Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Search in a Binary Search Tree

EASYProblemSolveExternal Links

Description

You are given the root of a Binary Search Tree (BST) and an integer val.

Find the node in the BST whose value equals val and return the subtree rooted at that node. If no node with value val exists in the tree, return null.

Recall that a BST is a binary tree where every node satisfies:

  • All values in the left subtree are less than the node's value
  • All values in the right subtree are greater than the node's value
  • Both left and right subtrees are themselves BSTs

Examples

Example 1

Input: root = [4, 2, 7, 1, 3], val = 2

Output: [2, 1, 3]

Explanation: The tree looks like:

        4
       / \
      2   7
     / \
    1   3

We search for val = 2. Node 2 exists in the tree. We return the entire subtree rooted at node 2, which includes nodes 2, 1, and 3 — represented as [2, 1, 3].

Example 2

Input: root = [4, 2, 7, 1, 3], val = 5

Output: []

Explanation: Using the same tree:

        4
       / \
      2   7
     / \
    1   3

We search for val = 5. Starting at root 4, since 5 > 4 we go right to node 7. Since 5 < 7 we would go left, but node 7 has no left child. Therefore val = 5 does not exist in the tree and we return null (empty).

Example 3

Input: root = [4, 2, 7, 1, 3], val = 7

Output: [7]

Explanation: Node 7 exists as a leaf node (no children). We return the subtree rooted at 7, which contains only node 7 itself.

Constraints

  • 1 ≤ Number of nodes ≤ 5000
  • 1 ≤ Node.val ≤ 10^7
  • root is a valid binary search tree
  • 1 ≤ val ≤ 10^7

Editorial

Brute Force

Intuition

The simplest way to find a value in any tree — BST or not — is to visit every single node and check whether its value matches the target. This is exactly what a depth-first search (DFS) does: start at the root, visit the current node, then recursively visit the left subtree and the right subtree.

Think of it like searching for a specific book in a library by walking through every shelf from start to finish. You do not use the alphabetical ordering of the shelves — you just check each book one by one until you find it.

This approach completely ignores the BST property. It works on any binary tree, not just BSTs. While that makes it simple and general-purpose, it also means we waste time visiting nodes we could have skipped.

Step-by-Step Explanation

Let's trace through with root = [4, 2, 7, 1, 3], val = 2:

        4
       / \
      2   7
     / \
    1   3

Step 1: Start DFS at root node 4. Compare: is 4 == 2? No.

Step 2: Since 4 ≠ 2, recurse into the left subtree. Visit node 2.

Step 3: Compare: is 2 == 2? YES! We found the target node.

Step 4: Return the subtree rooted at node 2, which is [2, 1, 3].

Notice that this DFS happened to go left first and found the node quickly. But if we had searched for val = 7, the DFS would first explore the entire left subtree (nodes 2, 1, 3) before finally reaching node 7 on the right. That is 4 wasted node visits — the BST property tells us immediately that 7 > 4 means we should go right, but brute force DFS ignores this entirely.

Brute Force DFS — Searching Without BST Property — Watch how a generic DFS visits nodes without leveraging the BST ordering. It checks every node until it finds the target.

Algorithm

  1. If root is null, return null (value not found)
  2. If root.val equals val, return root (found the target subtree)
  3. Recursively search the left subtree. If it returns a non-null result, return that result
  4. Otherwise, recursively search the right subtree and return whatever it returns
  5. The search explores both subtrees regardless of the BST ordering

Code

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // Base case: node is null
        if (root == nullptr) return nullptr;
        
        // Check current node
        if (root->val == val) return root;
        
        // Search left subtree first
        TreeNode* leftResult = searchBST(root->left, val);
        if (leftResult != nullptr) return leftResult;
        
        // If not in left, search right subtree
        return searchBST(root->right, val);
    }
};
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # Base case: node is null
        if not root:
            return None
        
        # Check current node
        if root.val == val:
            return root
        
        # Search left subtree first
        left_result = self.searchBST(root.left, val)
        if left_result:
            return left_result
        
        # If not in left, search right subtree
        return self.searchBST(root.right, val)
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // Base case: node is null
        if (root == null) return null;
        
        // Check current node
        if (root.val == val) return root;
        
        // Search left subtree first
        TreeNode leftResult = searchBST(root.left, val);
        if (leftResult != null) return leftResult;
        
        // If not in left, search right subtree
        return searchBST(root.right, val);
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, the target value is not in the tree (or is the last node visited). The DFS must visit every node exactly once, giving O(n) time regardless of the tree's shape or the BST property.

Space Complexity: O(h)

The recursion stack grows as deep as the tree's height h. For a balanced BST, h = O(log n). For a skewed BST (essentially a linked list), h = O(n). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force DFS treats the BST as a generic binary tree, ignoring its most powerful property: ordering. In a BST, all values in the left subtree are smaller than the root, and all values in the right subtree are larger. This means that at every node, we can determine with a single comparison which half of the tree to search — exactly like binary search on a sorted array.

By not using this property, the brute force may visit all n nodes even when the target is at the root's immediate right child. For example, searching for val = 7 in our tree would cause DFS to explore the entire left subtree (nodes 2, 1, 3) before reaching 7 — three completely unnecessary visits.

With n up to 5000, the O(n) approach works within time limits, but we are leaving a logarithmic speedup on the table. A BST-aware search visits at most h nodes (one per level), where h = O(log n) for balanced trees. For n = 5000, that is ~13 comparisons instead of 5000.

The key insight: at each node, compare val with the node's value. If val is smaller, go left. If val is larger, go right. If equal, we found it. This eliminates half the remaining tree at every step — just like binary search.

Better Approach - Recursive BST Search

Intuition

Now we leverage the BST property. At each node, instead of blindly exploring both subtrees, we make an informed decision:

  • If val equals the current node's value → we found the target. Return this node.
  • If val is less than the current node's value → the target must be in the left subtree (all right subtree values are larger, so the target cannot be there).
  • If val is greater than the current node's value → the target must be in the right subtree.

This is exactly how you look up a word in a dictionary: you open to a page, check if the word comes before or after, and flip accordingly. You never need to read every page.

The recursive version expresses this logic naturally: the function calls itself on either the left or right child based on the comparison.

Step-by-Step Explanation

Let's trace through with root = [4, 2, 7, 1, 3], val = 2:

        4
       / \
      2   7
     / \
    1   3

Step 1: Start at root node 4. Compare val = 2 with node value 4.

Step 2: 2 < 4, so by the BST property, val must be in the left subtree. We completely skip the right subtree (node 7). Recurse left.

Step 3: Now at node 2. Compare val = 2 with node value 2.

Step 4: 2 == 2! The values match. Return node 2 and its entire subtree [2, 1, 3].

We visited only 2 nodes (4 and 2) and skipped node 7 entirely. Compare this with the brute force, which could potentially visit all 5 nodes for certain targets.

Recursive BST Search — Guided by the BST Property — Watch how the BST property guides us to the target node by eliminating half the tree at each step, like binary search on a sorted structure.

Algorithm

  1. If root is null, return null (val not in tree)
  2. If root.val equals val, return root (found the target)
  3. If val < root.val, recurse on root.left (target must be in left subtree)
  4. If val > root.val, recurse on root.right (target must be in right subtree)
  5. Each recursive call processes exactly one node per level — we never branch into both subtrees

Code

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // Base case: not found
        if (root == nullptr) return nullptr;
        
        // Found the target
        if (root->val == val) return root;
        
        // BST property: go left if val is smaller
        if (val < root->val)
            return searchBST(root->left, val);
        
        // BST property: go right if val is larger
        return searchBST(root->right, val);
    }
};
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # Base case: not found
        if not root:
            return None
        
        # Found the target
        if root.val == val:
            return root
        
        # BST property: go left if val is smaller
        if val < root.val:
            return self.searchBST(root.left, val)
        
        # BST property: go right if val is larger
        return self.searchBST(root.right, val)
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // Base case: not found
        if (root == null) return null;
        
        // Found the target
        if (root.val == val) return root;
        
        // BST property: go left if val is smaller
        if (val < root.val)
            return searchBST(root.left, val);
        
        // BST property: go right if val is larger
        return searchBST(root.right, val);
    }
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the BST

At each level of the tree, we make exactly one comparison and move down one level. We visit at most h nodes (one per level). For a balanced BST, h = O(log n), giving O(log n) time. For a completely skewed BST (like a linked list), h = O(n), giving O(n) worst-case time.

Space Complexity: O(h)

Each recursive call adds one frame to the call stack, and we recurse to a maximum depth of h. For a balanced tree, this is O(log n). For a skewed tree, this is O(n). This stack space is the key disadvantage compared to the iterative approach.

Why This Approach Is Not Efficient

The recursive BST search achieves O(h) time — a significant improvement over the O(n) brute force. However, it uses O(h) extra space for the recursion call stack.

For a balanced BST with n = 5000 nodes, h ≈ 12, so the stack depth is modest. But for a skewed BST (where every node has only one child, forming a linked-list shape), h = n = 5000. That means 5000 nested recursive calls, each consuming stack memory for local variables, the return address, and the function frame.

In languages with limited stack sizes, deep recursion risks a stack overflow. Even when it does not crash, the overhead of function calls — argument passing, frame allocation, return value propagation — adds constant-factor cost per level.

The key insight: the BST search follows a simple path from root to the target (or to a null leaf). There is no branching, no backtracking, no fan-out. This linear, non-branching path is a perfect candidate for a while loop — which uses O(1) extra space.

Optimal Approach - Iterative BST Search

Intuition

The recursive BST search makes one decision per node: go left, go right, or return the match. There is no need to remember where we came from because we never backtrack. The search is a straight line from root to target (or to a null pointer).

A straight-line path with no backtracking is the simplest possible pattern for a loop. We replace the recursive function with a while loop:

  • Maintain a curr pointer starting at root
  • At each iteration, compare curr.val with val
  • If equal, return curr
  • If val is smaller, move curr to curr.left
  • If val is larger, move curr to curr.right
  • If curr becomes null, the value is not in the tree

This is like using your finger to trace a path through a dictionary's table of contents: you slide your finger left or right based on alphabetical ordering, never lifting it off the page (no stack needed).

Step-by-Step Explanation

Let's trace through with root = [4, 2, 7, 1, 3], val = 2:

        4
       / \
      2   7
     / \
    1   3

Step 1: Initialize curr = root (node 4).

Step 2: Compare: curr.val = 4 vs val = 2. Since 2 < 4, move curr to curr.left (node 2).

Step 3: Compare: curr.val = 2 vs val = 2. They are equal!

Step 4: Return curr (node 2 and its subtree [2, 1, 3]).

The while loop ran for only 2 iterations. We visited exactly 2 nodes and used zero extra space beyond the curr pointer. The same O(h) time as the recursive version, but with O(1) space.

Iterative BST Search — While Loop with Zero Extra Space — Watch the curr pointer trace a path from root to target using only a while loop. No recursion stack needed — just one pointer sliding down the tree.

Algorithm

  1. Set curr = root
  2. While curr is not null:
    a. If curr.val == val, return curr (found the target)
    b. If val < curr.val, set curr = curr.left (search left subtree)
    c. If val > curr.val, set curr = curr.right (search right subtree)
  3. If the loop exits (curr becomes null), return null (val not in tree)

Code

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* curr = root;
        
        while (curr != nullptr) {
            if (curr->val == val)
                return curr;
            else if (val < curr->val)
                curr = curr->left;
            else
                curr = curr->right;
        }
        
        // val not found in the BST
        return nullptr;
    }
};
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        curr = root
        
        while curr:
            if curr.val == val:
                return curr
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        
        # val not found in the BST
        return None
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode curr = root;
        
        while (curr != null) {
            if (curr.val == val)
                return curr;
            else if (val < curr.val)
                curr = curr.left;
            else
                curr = curr.right;
        }
        
        // val not found in the BST
        return null;
    }
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the BST

Each iteration of the while loop processes one node and moves one level down. The loop runs at most h times (once per level). For a balanced BST with n = 5000 nodes, h ≈ 12, so we do at most ~12 comparisons. For a skewed BST, h = n in the worst case.

Space Complexity: O(1)

We use only a single pointer variable curr. No recursion stack, no auxiliary data structures. This is the key improvement over the recursive approach — same time complexity, but constant extra space regardless of tree shape.