BST Operations

Search and insert in a BST are easy — walk left or right and you’re done. Then the interviewer asks you to delete a node that has two children, and suddenly it’s the question that separates the prepared from the panicking. You can’t just remove it; both subtrees need a home. The fix is one elegant idea — and once you see it, the whole problem is trivial.

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.

A BST. Inorder gives: 1, 3, 4, 6, 7, 8, 10, 14 — sorted.

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                 14

Case 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)

Predict first

You're deleting a BST node that has TWO children. You can't just drop it. Which existing value should take its place to keep the BST valid — and where do you find it?

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                  14

The complete delete code

Recall the two-children core

Fill in the walk that locates the in-order successor:

python · fill in the blanks0/1 hints

# the node to delete has TWO children:
succ = node.right                 # start in the right subtree
while succ.left is not None:
  # ??? step toward the inorder successor
node.val = succ.val               # copy the successor's value up
node.right = delete(node.right, succ.val)   # then delete the successor

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 ancestor

This 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.

Quick check

You need O(1) average lookups by key AND nothing else (no ordering, no range queries). Hash map or BST-backed ordered map?

That completes Day 6 — you can search, insert, and delete in a BST, and you know when ordering is worth the O(log n). Next: Day 7 — Heaps, the other tree-shaped structure, which gives up full ordering for O(1) access to the min or max — exactly the priority queue you met on Day 4.

Traversals Basic Questions

Finished this page?