Search in a BST
Search in a BST: return the subtree rooted at the node whose value equals val, or null.
- The number of nodes in the tree is in the range [1, 5000].
- 1 <= Node.val <= 10⁷
- root is a binary search tree.
- 1 <= val <= 10⁷
Intuition
Search in a BST is binary search with pointers instead of array indices. In an array you compare against the middle element and throw away half the range; in a BST you compare against the current node and throw away one of its subtrees. The mechanism is the same, and so is the payoff — each comparison eliminates a large fraction of what is left. What makes it work is the BST invariant: for any node, every value in the left subtree is smaller and every value in the right subtree is larger. That is a much stronger guarantee than it first sounds. It does not just order a node against its two children — it orders that node against every descendant. So one comparison at the root tells you which entire half of the tree the target could possibly be in. That gives a three-way decision at every step: - Equal means you have found it, and the problem asks for the subtree rooted here, so return the node itself rather than just true. - Target smaller means go left; nothing to the right can match. - Target larger means go right. The walk never backtracks, because a comparison never leaves ambiguity about which side to take. You either land on the value or fall off the bottom of the tree, and falling off means the value was never there.
A BST turns searching into deciding: at every node one comparison eliminates an entire subtree. Whenever the structure tells you which way to go rather than forcing you to try both, the traversal is a walk, not a search — so it's O(h) and needs no stack, no queue, no recursion.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(h) time and O(1) space.
Start a cursor at the root
Point a single variable at the root and let the loop move it downward. No stack or queue is needed — unlike most tree problems, this one follows exactly one path and never has to remember where it has been.
Compare and take the three-way branch
At each node compare val against node.val. Equal ends the search. Smaller moves left, larger moves right. Each comparison discards an entire subtree, which is the reason this beats scanning all n nodes.
Return the node, not a boolean
The problem asks for the subtree rooted at the matching node, so return the node object itself. Its children come along for free, since a node in a tree already carries everything below it. Returning true here is a common misread of the problem statement.
Falling off the tree means not found
If the cursor becomes null, you have followed the path the value would have taken and it was not there. Return null. There is no other way for the search to fail — every step was forced by a comparison, so no backtracking is needed to be sure.
Prefer the iterative loop over recursion
A while node: loop does this in constant space, whereas the recursive version costs O(h) stack frames for no benefit. This is genuine tail recursion — the recursive call is the last thing that happens — so there is nothing the stack is actually keeping track of.
Cost is the height of the tree
The walk takes one step per level, so time is O(h). A balanced BST gives O(log n), which is the whole reason BSTs are used. A degenerate tree — one built by inserting already-sorted values — collapses into a linked list and degrades to O(n).
Where self-balancing trees come in
That O(n) worst case is what AVL and red-black trees exist to prevent. They rebalance on insertion so the height stays O(log n), which keeps this search fast regardless of the order the data arrived in. Mentioning that trade-off is usually what an interviewer is listening for.
Solution & live demo
Common pitfalls
Searching both subtrees like a plain binary tree
if not root or root.val == val: return root return self.searchBST(root.left, val) or self.searchBST(root.right, val)
while root and root.val != val:
root = root.left if val < root.val else root.right
return rootThis returns the right node but visits every node, making it O(n) and throwing away the only thing a BST gives you. The ordering means a smaller target cannot possibly be on the right, so half the tree is ruled out at each step without looking at it.
Returning None instead of the subtree on a miss
while root:
if root.val == val: return root
root = root.left if val < root.val else root.right
return Nonewhile root and root.val != val:
root = root.left if val < root.val else root.right
return rootBoth are correct here, but the problem asks for the subtree rooted at the match, and the loop-condition form returns exactly that in one exit — the loop stops either on the match or on None, which is already the required answer.
Edge cases
Walk falls off a null child → return None.
Loop exits immediately.