Pattern visualizer
BST Search
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. 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.
time O(h) — O(log n) balanced, O(n) skewedspace O(1)step 1 / 13
1
3
6
8
10
13
14
Call stack
bstSearch(6)node → 8
line 1
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.
Pseudocode
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