BST Operations
A Binary Search Tree keeps its values in an order that mirrors binary search on an array. For every node:
- All values in the left subtree are less than the node.
- All values in the right subtree are greater than the node.
- Both subtrees are themselves BSTs.
That invariant turns three operations — search, insert, delete — into O(log n) on a balanced tree.
Search
Walk down from the root. At each node, the BST property tells you whether the target is to the left or the right. Constant work per level → O(height) total.
The iterative version uses O(1) extra space. A recursive version is just as correct but adds O(h) call-stack frames.
Insert
Same downward walk. When you hit a null spot — that’s where the new value belongs.
The “reassign-and-return” pattern is the cleanest recursive style: the function returns the new (possibly mutated) subtree root. The caller wires it back into the parent. We’ll use this same pattern for delete, where it really shines.
Insertion order matters for the shape of the tree. Inserting 1, 2, 3, 4, 5 into an empty BST produces a degenerate right-leaning chain — O(n) operations forever. Self-balancing trees (AVL, Red-Black) prevent this; plain BSTs do not.
Delete — the tricky one
Deletion has three cases, and the third is what makes interviewers love this problem.
Case 1: the node has no children
Just remove it. Set the parent’s pointer to null.
8 8
/ \ / \
3 10 delete(7) 3 10
/ \ → \
7 14 14Case 2: the node has exactly one child
Replace the node with its child.
8 8
/ \ / \
3 10 delete(3) 4 10
\ \
4 14
\
... (4 takes 3's place)Case 3: the node has two children
This is the famous one. We can’t just “drop” the node — it has two subtrees to preserve.
The trick: find the in-order successor (the smallest value in the right subtree) — that’s the smallest value that’s still larger than the deleted value, so it preserves the BST order. Copy its value into the node being deleted, then recursively delete the successor from the right subtree (which falls into case 1 or 2).
8 9 ← 9 was the successor of 8
/ \ / \
3 10 delete(8) 3 10
/ \ → \
9 14 14The complete delete code
Why the in-order successor specifically? Because it’s the smallest value strictly greater than the deleted node. Replacing the node with this value preserves the property that everything in the left subtree is less than the node, and everything in the right subtree is greater. The in-order predecessor (largest value in the left subtree) would also work — pick either, but pick consistently.
Inorder successor & predecessor
Useful primitives in their own right:
- Successor of node
x= the next-larger value in the BST. - Predecessor of node
x= the next-smaller value.
If x has a right subtree, the successor is the leftmost node of that subtree. Otherwise, walk up to the lowest ancestor where x is in the left subtree.
def successor(root, x):
if x.right:
n = x.right
while n.left: n = n.left
return n
# No right subtree — walk up until we go up a "left" link
cur, ancestor = root, None
while cur != x:
if x.val < cur.val:
ancestor = cur
cur = cur.left
else:
cur = cur.right
return ancestorThis is how some C++ iterators on std::set and std::map implement ++.
A complete BST class
Putting it all together:
Complexity, in one table
| Operation | Average (balanced) | Worst (skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Min / Max | O(log n) | O(n) |
| Inorder traversal | O(n) | O(n) |
| Build BST from n sorted values | O(n log n) worst | — |
The worst case is when the tree degenerates to a linked list. Self-balancing variants (AVL, Red-Black) prevent this — every operation becomes O(log n) guaranteed.
When to actually use a BST
Almost never write one from scratch in production. Reach for:
- Python:
sortedcontainers.SortedList(B-tree-like in practice). - C++:
std::set/std::map/std::multiset(Red-Black tree). - Java:
TreeSet/TreeMap(Red-Black tree).
Implementing a BST from scratch is the interview exercise. The real exercise — picking when to use the stdlib’s ordered map vs hash map — is what you’ll do every day:
| You need… | Hash map | Ordered map (BST-backed) |
|---|---|---|
| O(1) lookups, no ordering | ✅ | ❌ |
| Iteration in sorted order | ❌ | ✅ |
| Range queries (“everything in [a, b]”) | ❌ | ✅ |
| Find next-larger / next-smaller | ❌ | ✅ |
| Predictable worst-case | ⚠️ (hash attacks) | ✅ |
Use a hash map by default. Reach for an ordered map (which is BST under the hood) when you need order.
Now you have the foundation for every tree problem. Time to go practice.