Search in a BST is the cleanest demonstration of why we build binary search trees in the first place. The ordering rule turns a lookup into a series of left-or-right decisions, each one throwing away half of what is left.
Problem. You are given the root of a binary search tree and an integer target. Return the
node whose value equals target, or None if no such node exists. A BST guarantees that for every
node, all values in its left subtree are smaller and all values in its right subtree are larger.
Example: searching the tree rooted at 8 (children 3 and 10) for target = 6 returns the node
holding 6, reached by the path 8 → 3 → 6.
The slow way first
If you ignored the ordering, you could walk the entire tree — visit every node and check its value. That works on any tree, but it is O(n): for a tree with a million nodes you might inspect all million.
The question to ask: the tree is sorted in a special way — can the comparison at each node tell me where NOT to look? Yes. The BST property means one comparison rules out a whole subtree.
The idea: let the comparison steer you
Start at the root and keep a pointer cur. At each node, compare target with cur.value:
- If they are equal, you found it — return
cur. - If
targetis smaller, the answer can only be in the left subtree, so move left. - If
targetis larger, move right.
Each step discards the other half of the tree. When cur falls off the bottom (None), the value is not present.
The key insight: a single comparison eliminates an entire subtree, so we never waste time on values that cannot match.
Walk through it
Step through the animation. The cur pointer starts at the root 8. Since 6 < 8, the whole right subtree (rooted at 10) dims out — we will never look at it. We drop to 3; now 6 > 3, so the left child 1 dims and we go right. That lands us on 6, which equals the target. We touched just three nodes instead of all six.
Pseudocode
cur = root
while cur is not None:
if cur.value == target:
return cur # found it
if target < cur.value:
cur = cur.left # answer is in the left subtree
else:
cur = cur.right # answer is in the right subtree
return None # fell off the tree -> not presentThe Python solution
def search_bst(root, target):
cur = root
while cur is not None:
if cur.value == target:
return cur
if target < cur.value:
cur = cur.left
else:
cur = cur.right
return Nonecuris the node we are currently standing on; it starts at the root.- The
whileloop keeps walking as long as we have not fallen off the tree. cur.value == targetis the success case — we return that node immediately.target < cur.valuesends us left (toward smaller values); theelsesends us right.- If the loop exits because
curbecameNone, the target was never in the tree, so we returnNone.
Complexity
| Case | Time | Notes |
|---|---|---|
| Balanced tree | O(log n) (fast) | halve the search space each hop |
| Worst case (degenerate) | O(n) (moderate) | a tree shaped like a linked list |
O(1) (fast)The iterative version uses only a single pointer, so it is O(1) extra space. On a balanced BST the height is log n, which is why a lookup over a million nodes costs roughly twenty comparisons.
When this pattern shows up
Whenever data is held in a BST and you need to find, insert, or delete a value, the move is the same: compare with the current node and walk down one side. Insertion follows the identical path and drops the new node where the walk falls off; deletion finds the node the same way first.
This O(log n) bound assumes the tree is reasonably balanced. If values were inserted in sorted order, the BST degenerates into a chain and search degrades to O(n). Self-balancing trees (AVL, red-black) exist precisely to keep the height at log n.
Practice
Searching the same tree for target = 14, what path does cur take from the root?
1. At a node with value 8, the target is 6. Which way do we go?
2. Why is search O(log n) on a balanced BST?
3. What does the loop return when cur becomes None?
4. When can this search degrade to O(n)?