Search in a Binary Search Tree: Follow the Only Path That Can Hold Your Target

A Binary Search Tree is a sorted array's smarter cousin. The same ordering that makes binary search fast on an array is baked into every node of a BST — and searching one is the cleanest possible demonstration of why that ordering is worth so much.

The task sounds trivial: find a value in a tree. What makes it a pattern worth learning is the single decision you make at each node — left or right — that throws away half of everything still in play. Get comfortable with that decision here and Insert, Delete, and Lowest Common Ancestor all fall out of the same reasoning.

The problem#

You're given the root of a Binary Search Tree and an integer val. Return the subtree (the node) whose value equals val. If no node holds that value, return null.

The BST invariant is the whole game: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger.

Because the tree is sorted, you never have to guess which way to go. The comparison at each node tells you.

The brute force baseline#

Ignore the ordering and a BST is just a binary tree. You could search it the way you'd search any tree — visit every node until you stumble onto the target:

This is correct, but it's blind. It explores both children at every node because it has no reason to prefer one over the other. In a tree of n nodes that's O(n) work — you might visit all of them before finding your value or proving it's absent. For a tree with a million nodes, that's a million comparisons for something the ordering could have answered in about twenty.

The waste is obvious once you name it: when you're standing on node 4 looking for 3, scanning the right subtree (7 and everything under it) is pointless. Every value over there is greater than 4, and 3 is less than 4. You already know it can't be there.

The key insight: let the comparison pick the direction#

The BST invariant turns each node into a signpost. Compare your target with the current node's value and exactly one of three things is true:

• val === node.val — you found it. Stop.
• val < node.val — the target, if it exists, is in the left subtree. The entire right subtree is eliminated.
• val > node.val — the target is in the right subtree. The entire left subtree is eliminated.

This is BST directed search: at every step you follow the only subtree that can still contain the target and discard the other half. It's binary search — the same halving that makes a sorted array searchable in O(log n) — walked over tree pointers instead of array indices. You never explore two branches, so there's no recursion tree to fan out. It's a single straight-line descent from root toward a leaf.

The optimal solution#

Because the search only ever moves in one direction, you don't need recursion or a stack at all. A loop that reassigns a single pointer does the job with O(1) extra space:

Three lines carry the whole idea. The while keeps descending as long as there's a node to inspect. The if is the success exit. The reassignment is the directed step: the ternary picks root.left when the target is smaller and root.right when it's larger, so root marches down exactly one path. Fall out of the loop — meaning you walked off the tree into a null child — and the value simply isn't there, so you return null.

Walkthrough#

Trace searchBST(root, 3) on the tree [4, 2, 7, 1, 3]. The root pointer starts at the top and moves down; each iteration eliminates a subtree.

Three comparisons, done. Notice what iteration 1 bought you: the moment you saw 3 < 4, the node 7 and everything it could ever hold vanished from consideration. In a bigger, deeper tree that one decision might discard thousands of nodes. Each row of this table is one halving of the search space.

Now trace searchBST(root, 5) on the same tree to see the miss case: 5 > 4 sends you right to 7, 5 < 7 sends you left to 7.left, which is null. The loop condition fails, you return null — and you proved absence in two hops without touching the left half of the tree at all.

Complexity#

Here h is the height of the tree. For a balanced BST, h ≈ log₂(n), so a lookup in a million-node tree takes about 20 comparisons. The iterative version uses no stack — just the root variable being reassigned — so its extra space is O(1). A recursive version has the same O(h) time but pays O(h) space for the call stack.

The honest caveat: if the tree is degenerate — inserted in sorted order so it's really a linked list — then h = n and search degrades to O(n). O(log n) is a promise the tree only keeps while it stays balanced.

Common mistakes#

• Exploring both subtrees. The single biggest error is writing tree search that recurses left and right. That throws away the entire point of a BST and lands you back at O(n). The comparison exists precisely so you pick one side.
• Getting the direction backwards. val < root.val means go left (toward smaller values). Flipping it sends you chasing the wrong half and you'll "not find" values that are sitting right there.
• Forgetting the null check drives termination. The while (root !== null) isn't decoration — it's the miss case. Walking off the tree into a null child is exactly how you prove a value is absent. Drop it and you'll dereference null.
• Reaching for recursion by reflex. Recursion works and reads fine, but on a directed search it only adds O(h) stack space. The loop is strictly leaner here.
• Assuming balance you don't have. O(log n) holds only for a balanced tree. If insertions arrive sorted, the tree tips over into a chain and every guarantee evaporates.

Where this pattern shows up next#

The compare-and-descend move is the foundation for nearly every BST operation:

• Insert into a Binary Search Tree — same descent, but you keep going until you hit a null child and hang the new node there.
• Validate Binary Search Tree — flips the lens to check that the ordering invariant this search relies on actually holds everywhere.
• Lowest Common Ancestor of a Binary Search Tree — descends until two targets split to opposite sides, using the exact same comparison logic.
• Kth Smallest Element in a BST — trades directed search for an in-order traversal that reads the tree in sorted order.

You can also step through the search interactively to watch the current node light up and each discarded subtree fade at every comparison.

FAQ#

What is the time complexity of searching a Binary Search Tree?#

It's O(h), where h is the height of the tree. For a balanced BST that height is about log₂(n), so a lookup among a million nodes takes roughly 20 comparisons — the same logarithmic speed as binary search on a sorted array. The worst case is a degenerate tree that has collapsed into a linked list (nodes inserted in sorted order), where h equals n and search slows to O(n).

Should I search a BST iteratively or recursively?#

Both are O(h) in time and equally correct, so it's mostly style. The iterative loop is leaner on space: it reassigns one root pointer and uses O(1) extra memory, while recursion adds an O(h) call stack. Since a directed search only ever moves down one path, there's nothing for recursion to "remember" on the way back, which makes the loop the more natural fit.

Why is searching a BST faster than searching a plain binary tree?#

The Binary Search Tree ordering lets you skip half the remaining nodes at every step. Comparing your target against the current node tells you which subtree it must live in, so you follow exactly one child and discard the other entirely. A plain binary tree has no such ordering, so you're forced to explore both children and potentially visit all n nodes.

What does the search return when the value isn't in the tree?#

It returns null. In the iterative solution, the while (root !== null) loop keeps descending until either a node matches — returning that node — or you follow a child pointer that leads to null, meaning you've walked past a leaf without a match. Falling out of the loop is the tree's way of proving the value cannot exist, and it happens in at most O(h) steps.