Binary search tree
Every node keeps smaller values on its left and the rest on its right. Inserting and searching both start at the root and choose a side at each node, so the work depends on the height of the tree, not the number of values.
empty tree
Insert 9 values one at a time, then look for 7. Smaller values go left, others go right.
1function insert(root, value) {2 if (root === null) return { value, left: null, right: null };3 if (value < root.value) root.left = insert(root.left, value);4 else root.right = insert(root.right, value);5 return root;6}78function contains(root, target) {9 let node = root;10 while (node !== null) {11 if (target === node.value) return true;12 node = target < node.value ? node.left : node.right;13 }14 return false;15}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | log n | a balanced tree: each step halves what is left |
| average | log n | values inserted in random order |
| worst | n | sorted input builds a chain |
| space | n | one node per value |
Where it breaks
- Sorted input. Pick Sorted input: each value is bigger than all before it, so every one goes right and the tree is a chain. Finding 7 takes 7 steps, the same as a linear search. Balanced trees like AVL and red-black fix this.
- The shape depends on the order. The same values inserted in a different order give a different tree. Shuffling before inserting gives a height of about log n on average.
- Duplicates. This version sends equal values to the right, so they pile up as a chain. Many real trees store a count on the node instead.