Binary search tree
mediumOne comparison discards an entire subtree - binary search expressed in pointers. Then insert sorted keys and watch it degenerate into a linked list, which is why balanced trees exist.
O(log n)Average O(log n)Worst O(n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How binary search tree works
A binary search tree keeps one promise at every node: every key in node.left is smaller, every key in node.right is larger. Search leans on that directly - one comparison against 50 discards whichever half of the tree sits on the wrong side. It is the halving of binary search, expressed in pointers instead of array indices, and insert is the same walk, ending by attaching a leaf at the first null pointer.
Every operation walks one root-to-leaf path, so every cost is really O(h), the height - and h is only log n when the shape cooperates. Insert 9 sorted keys and each attaches to the right of the previous one: a 9-deep chain, and search becomes a linear scan. Balanced shape is an accident of arrival order, which is exactly the accident AVL and red-black trees refuse to permit.
Deletion has three cases, graded by child count. A leaf simply unlinks. One child splices through - that subtree is already on the correct side of the parent. Two children is the real case: overwrite the node's key with its in-order successor - one step right, then left forever - then delete the successor from the right subtree instead, which is easy because by construction it has no left child.
Step by step
- Insert 50, 30, 70, 20, 40 in that order. Each key descends by comparisons until it hits a null pointer, then attaches there as a leaf.
- Search 40: 40 < 50 goes left, 40 > 30 goes right, found - three comparisons, one per level.
- Delete 30, a node with two children - the hard case. Its subtrees rooted at 20 and 40 both need a home.
- Find the in-order successor: step right to 40, then left as far as possible. 40 has no left child, so 40 is the successor.
- Copy 40 into the deleted node's slot. For a moment the tree holds 40 twice.
- Delete the original 40 from the right subtree. It has no left child by construction, so it splices out via the easy case.
- Final tree: 50 at the root, 40 on the left holding 20, 70 on the right. An in-order walk still comes out sorted.
Complexity
| Best case time | O(log n) |
|---|---|
| Average time | O(log n) |
| Worst case time | O(n) |
| Space | O(n) |
Everything is O(h), and h is only log n if the tree stays balanced.
Reference implementation
Python
def search(node, k):
while node:
if k == node.key:
return node
node = node.left if k < node.key else node.right
return None
def insert(node, k):
if node is None:
return Node(k)
if k < node.key:
node.left = insert(node.left, k)
elif k > node.key:
node.right = insert(node.right, k)
return node # duplicates ignored
def delete(node, k):
if node is None:
return None
if k < node.key:
node.left = delete(node.left, k)
elif k > node.key:
node.right = delete(node.right, k)
else:
if node.left is None: return node.right # 0 or 1 child
if node.right is None: return node.left
succ = node.right # 2 children:
while succ.left: # in-order successor
succ = succ.left
node.key = succ.key
node.right = delete(node.right, succ.key)
return nodeJavaScript
function search(node, k) {
while (node) {
if (k === node.key) return node;
node = k < node.key ? node.left : node.right;
}
return null;
}
function insert(node, k) {
if (!node) return { key: k, left: null, right: null };
if (k < node.key) node.left = insert(node.left, k);
else if (k > node.key) node.right = insert(node.right, k);
return node;
}Worth noticing
The BST property is what makes search O(h)
Everything left of a node is smaller, everything right is larger. So one comparison discards an entire subtree - the same halving as binary search, expressed in pointers.
O(h), not O(log n)
Height is only log n if the tree is balanced. Insert sorted keys and the tree degenerates into a linked list with h = n, and every operation becomes linear. This failure is exactly why AVL and red-black trees exist.
Deletion with two children is the only hard case
You cannot simply remove the node - it has two subtrees to reattach. The fix is to overwrite its key with the in-order successor (the smallest key in the right subtree), which by construction is larger than everything left and smaller than everything else right, then delete that successor - which has at most one child.
In-order successor = go right once, then left forever
The next-largest key must be in the right subtree, and within that subtree it is the leftmost node. That two-line walk is worth memorising - it turns up in iterators and range queries too.
Common pitfalls
- Losing the returned subtree in recursive delete. The pattern is node.left = delete(node.left, k) - drop that assignment and the spliced child silently vanishes.
- Copying the successor's key but forgetting to delete the successor node itself - the tree now holds the key twice, and in-order output shows the duplicate.
- Mishandling the case where the deleted node's right child is itself the successor - relinking through the wrong parent detaches a whole subtree.
- Assuming O(log n). Feed a BST sorted input and every operation degrades to O(n) - test with adversarial insertion order before trusting it.
- Having no duplicate policy. This implementation treats an equal key as a no-op; mixing that silently with count-based or lean-left conventions corrupts assumptions later.
Where it is used
- The ordered maps of standard libraries - std::map, Java's TreeMap - are BSTs kept balanced by red-black rules.
- Range scans and order queries: floor, ceiling, nearest key, k-th smallest - questions a hash table cannot answer.
- In-memory indexes where sorted iteration matters as much as point lookup.
- Interview staples: validate a BST, lowest common ancestor, in-order successor, convert a sorted array to a balanced BST.
Frequently asked questions
What is the time complexity of BST insert, search and delete?
Best and average case O(log n), worst case O(n), with O(n) space for the tree itself. Every operation walks one root-to-leaf path, so everything is O(h) - and h is only log n if the tree stays balanced. Sorted insertions collapse it into a chain where h equals n.
What is the difference between a binary search tree and a heap?
A BST orders globally - the whole left subtree is smaller, the whole right larger - so it can find any key and iterate in sorted order. A heap orders only parent against child, so it can do one thing: serve the minimum or maximum. In exchange it lives in a plain array and builds in O(n).
What is an in-order successor and why does deletion use it?
The smallest key larger than the node's: one step right, then left as far as possible. Deleting a two-child node by copying the successor's key preserves the BST property, because that key is larger than everything left of the node and smaller than everything else on the right - and the successor itself has at most one child, so removing it is easy.
What happens if you insert sorted keys into a BST?
Each new key is larger than every existing one, so it descends to the rightmost node and attaches there. The result is a chain - height n, no branching - and search, insert, and delete all become O(n). Self-balancing trees like AVL exist precisely to make this arrival order harmless.