How Searching a Binary Search Tree Works
Searching a binary search tree discards one subtree at every node, like binary search over pointers. Its cost is the tree's height, so the shape of the tree matters more than its size.
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
Look for 55 in a balanced tree of 7 values, 3 levels deep.
Counters
- Comparisons
- 0
- Result
- -
- Tree height
- 3
- 7 nodes
- Worst case
- 3
- one compare per level
Settings
More options
Search
- 1
node = root - 2
while node: - 3
if target == node.value: return node - 4
if target < node.value: - 5
node = node.left - 6
else: - 7
node = node.right - 8
return NOT_FOUND
What each walk is for
| Walk | What you get | Time | Extra space |
|---|---|---|---|
| In-order | Values in sorted order | O(n) | O(h) |
| Pre-order | Root before children, for copying a tree | O(n) | O(h) |
| Post-order | Children before root, for freeing or evaluating | O(n) | O(h) |
| Level-order | Shallowest nodes first, level by level | O(n) | O(w) |
| Search | One value, by comparing at each node | O(h) | O(1) |
Scroll the table sideways for the rest of the columns.
n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n, which is what balancing prevents.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(1) | O(log n) | O(n) | O(1) |
How bst search works
Every node in a binary search tree splits the remaining values in two: smaller to the left, larger to the right. Searching compares the target with the node and follows one branch, discarding the other subtree entirely. Each step therefore costs one comparison and descends one level, so the total cost is the height of the tree: about log n if it is balanced, and n if it has degenerated into a chain.
Implementation
function bstSearch(root, target) {
let node = root;
while (node) {
if (node.value === target) return node;
// One comparison discards an entire subtree.
node = target < node.value ? node.left : node.right;
}
return null;
}
function bstInsert(root, value) {
if (!root) return { value, left: null, right: null };
if (value < root.value) root.left = bstInsert(root.left, value);
else if (value > root.value) root.right = bstInsert(root.right, value);
return root;
}When to use it
- Use a BST when you need ordered operations as well as lookups: ranges, predecessors, successors, and in-order iteration. A hash table beats it for plain key lookups and cannot do any of those.
- Use a self-balancing variant in production, red-black or AVL. Plain BSTs degrade to a list on sorted input, and sorted input is extremely common.
- Watch the height rather than the count: the visualiser's sorted-insert mode shows a tree of n nodes with height n, and searching it is a linear scan wearing a tree's clothes.