BST Search
Follow the ordering invariant down one root-to-leaf path to find a key.
A binary search tree keeps every left descendant smaller than its parent and every right descendant larger. That ordering lets search compare the target just once per level and walk a single root-to-leaf path, throwing away half of the remaining tree at every step instead of scanning all n nodes.
Details
Animated on: Given a binary search tree and a target key, return the node holding that key (or null if it is absent).
Follow the ordering invariant down one root-to-leaf path to find a key.
step 1 / 13
Call stack
Target is 6. Point node at the root, 8. A BST stores smaller keys to the left and larger keys to the right, so from any node one comparison discards a whole subtree.
1node = root2WHILE node is not null:3 IF target equals node's value:4 RETURN node (found it)5 ELSE IF target < node's value:6 node = node's left child (go smaller)7 ELSE:8 node = node's right child (go larger)9RETURN null (not in tree)
← / → step · space play · Home restart
Every step in words
Show all 13 steps
- Target is 6. Point node at the root, 8. A BST stores smaller keys to the left and larger keys to the right, so from any node one comparison discards a whole subtree.
- node holds 8, which is non-null, so we enter the loop and inspect this node.
- First test: is 6 equal to 8? No — 8 is not our target, so we must decide which side to descend.
- Is 6 < 8? Yes. Every key in 8's right subtree (10, 13, 14) is larger than 8, so 6 cannot be there — prune the whole right side and go left.
- node = node.left. The pointer drops to 3, the root of the surviving left subtree.
- node = 3 is non-null, so loop again and compare at this node.
- Is 6 equal to 3? No — we must descend one more level.
- Is 6 < 3? No — 6 is bigger than 3, so the left branch (which holds only 1) is ruled out.
- Since 6 > 3, the target can only be in 3's right subtree — take the else branch and go right.
- node = node.right. The pointer lands on 6.
- node = 6 is non-null — enter the loop one more time and compare.
- Is 6 equal to 6? Yes — this is exactly the node we were searching for.
- Return this node. We reached 6 in three comparisons (8 → 3 → 6) and never touched the right half of the tree — a balanced BST of n nodes needs only about log₂n steps.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.