Search in a Binary Search Tree — Solution

Problem

Given a binary search tree and a target integer, find the node whose value equals the target and return the entire subtree rooted at that node. If no such node exists, return null. The critical detail is that you return the subtree — the node and everything below it — not just the integer value.

[4,2,7,1,3]

• Input: root = [4, 2, 7, 1, 3], val = 2
• Output: [2, 1, 3]
• Explanation: Node 2 is found; its subtree (including children 1 and 3) is returned.

Searching for a missing value like val = 5 returns null because 5 does not appear anywhere in the tree.

Intuition

A BST is organized so that every node's left subtree contains only smaller values and its right subtree contains only larger values. At every node you face a binary decision: if the target is smaller, the answer can only live to the left; if larger, only to the right. You follow this single-direction chain until you either find the target or fall off the tree.

Approach 1 — Recursive

At each node, compare the target to the current value and recurse into the one subtree that could possibly contain it. The base cases handle both a successful match and exhausting the tree.

1. If the current node is null, the target is not in the tree — return null.
2. If the current node's value equals val, return the current node (this is the subtree root).
3. If val is less than the current value, recurse into the left child.
4. Otherwise, recurse into the right child.

1def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
2    # Null means not found; matching value means return this subtree
3    if not root or root.val == val:
4        return root
5    if val < root.val:
6        return self.searchBST(root.left, val)
7    return self.searchBST(root.right, val)

Time: O(h) where h is the tree height — O(log n) for a balanced BST, O(n) for a fully skewed one.
Space: O(h) — each recursive call adds a frame to the call stack.

Approach 2 — Iterative

Replace the recursion with a while loop, walking one pointer down the tree. This eliminates call-stack overhead without changing the traversal logic.

1. Initialize a current pointer to the root.
2. While current is not null:
   • If current.val equals val, return current.
   • If val is less than current.val, move current to its left child.
   • Otherwise, move current to its right child.
3. The loop exits only when current is null — the target was not found; return null.

1def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
2    current = root
3    while current:
4        if current.val == val:
5            return current
6        # BST property narrows the search to exactly one subtree each step
7        current = current.left if val < current.val else current.right
8    return None

Time: O(h) — identical traversal path to the recursive approach.
Space: O(1) — only a single pointer walks the tree; no call stack grows.

Complexity Summary

Common Mistakes

• Returning the integer value instead of the node — the problem asks for the subtree rooted at the matching node, not just root.val; returning the number passes simple tests but breaks any caller that needs to traverse the subtree.
• Searching both subtrees instead of one — ignoring the BST property and recursing into both children degrades the search from O(h) to O(n); the whole point of a BST is that the comparison eliminates one entire half.
• Swapping left and right — going right when val < root.val is a direction inversion; a reliable mnemonic is "smaller means left" since BST order mirrors sorted-array order: smaller indices are to the left.
• Mutating the root parameter in the iterative version — writing root = root.left instead of current = root.left overwrites the function's local reference to the tree root, which can silently corrupt the traversal if the compiler optimizes the parameter or if the variable is reused.
• Omitting the null return after the iterative loop — in Python the function implicitly returns None, which happens to be correct, but in Java or C++ the missing return is a compile error; always make the null case explicit.

Related Problems

• Kth Smallest Element in a BST — exploits BST inorder ordering to locate the kth value without visiting the whole tree
• Lowest Common Ancestor of a Binary Search Tree — uses the same left/right comparison logic to navigate toward two target nodes simultaneously
• Delete Node in a BST — first locates the target using this exact search, then restructures the subtree to maintain BST validity
• Convert Sorted Array to Binary Search Tree — constructs the BST whose structure makes this search pattern possible