BST Search —
Eliminate half the tree, every step.
Searching a BST is binary search adapted to a tree shape: compare against the current node, go left or right, and each comparison rules out an entire subtree. On a balanced tree that's O(log n) — the same guarantee as binary search on a sorted array. Watch the search path narrow on LearnBug and see why the BST property makes this possible.
What is BST Search?
Starting at the root, compare the target to the current node's value. Equal — found it. Smaller — the target can only be in the left subtree, so move left. Larger — move right. Repeat until you find the value or hit a None child, which means it isn't in the tree.
Why visualization helps
The BST property (left < node < right) is what makes eliminating an entire subtree in one comparison valid — but that's abstract until you see it. LearnBug highlights the whole subtree that gets ruled out at each step, not just the node being compared, so "eliminate half the tree" stops being a slogan and becomes something you watch happen.
BST search vs binary search on an array
Binary Search — sorted array
Split the search range in half using indices low/high. Guaranteed O(log n) because the array is always perfectly balanced by construction.
BST Search — tree ✓
Split by following left/right child pointers instead of indices. O(log n) only if the tree happens to be balanced — its shape depends on insertion history.
Worst case: skewed tree
If the tree degenerates into a linked list (e.g. built from already-sorted inserts), search becomes O(n) — no better than scanning a list.
Search for 3 in 4(2(1,3), 6)
At root 4: is 3 == 4? No. Is 3 < 4? Yes — go left
3 is smaller than 4, so by the BST property it cannot exist anywhere in 4's right subtree. That entire branch (node 6) is eliminated in one comparison.
At node 2: is 3 == 2? No. Is 3 < 2? No — go right
3 is larger than 2, so it must be in 2's right subtree. This eliminates node 1 (2's left child) from consideration.
At node 3: is 3 == 3? Yes — found
Two comparisons found the target in a 5-node tree — that's the O(log n) guarantee at work, halving the remaining candidates each time.
Return: True ✓ found in 2 comparisons out of 5 nodes
Recursive and iterative search
def search(node, target):
if node is None:
return False # hit an empty spot — not found
if node.val == target:
return True
if target < node.val:
return search(node.left, target)
return search(node.right, target)def search_iterative(root, target):
node = root
while node is not None:
if node.val == target:
return True
node = node.left if target < node.val else node.right
return FalseComplexity Notes
Frequently asked questions
How is BST search different from binary search on a sorted array?
Same underlying idea — eliminate half the remaining candidates each step — but binary search operates on index ranges into a contiguous array, guaranteed balanced by construction, while BST search follows child pointers whose balance depends entirely on insertion history.
What's the worst case for BST search?
A skewed tree — one built by inserting already-sorted values, for example — degenerates into a structure equivalent to a linked list. Every node has only one child, so search must potentially visit all n nodes: O(n), not O(log n).
Why does inorder traversal give sorted output if BST search relies on ordering?
They're two sides of the same property. The BST invariant — left < node < right, recursively — is exactly what makes both possible: it lets search eliminate a subtree per comparison, and it's exactly what inorder traversal (Left, Root, Right) reproduces as sorted order.
What if the value appears multiple times in the tree?
Standard BST search returns as soon as it finds any match, so it won't tell you how many times a value occurs or find every occurrence — the insertion convention (this hub sends duplicates right) determines where later occurrences end up, but you'd need a modified search to count them.
Watch half the tree disappear at every comparison
Paste your BST search into LearnBug and see the eliminated subtree highlighted at each step.