Binary Search Trees (BST): Search, Insert, Delete — and Why Order Changes Everything

In plain words

Think of a BST as a sorted filing cabinet where every folder is labeled with a number. If a new file's number is less than the label on the current drawer, it goes to the drawer on the left; if greater, it goes to the right. You never open more than one drawer at each step — so even in a cabinet with a million drawers, finding or adding a file takes only about 20 steps when the cabinet is balanced. That's the whole idea.

Lesson 10 gave trees shape; this lesson gives them purpose. Impose one ordering rule on a binary tree and you get a structure that can search like a sorted array, insert like a linked list, and iterate in sorted order — all at once. That combination is what neither arrays nor hash tables can offer: hash tables destroy order for O(1) lookup; sorted arrays keep order but pay O(n) per insertion. The BST keeps order *and* stays dynamic, charging O(h) — tree height — for everything.

The invariant, precisely

For every node: all keys in its left subtree are less than its key, and all keys in its right subtree are greater. The word *subtree* is load-bearing. A node's grandchildren, great-grandchildren — all of them obey the bound, not merely its immediate children. This is why the classic interview mistake (checking only child vs parent at each node) accepts invalid trees: a right-child's-left-descendant can be smaller than the grandparent while every local parent-child pair looks fine. (Duplicates: most treatments either disallow them or fix a convention like 'duplicates go right'; we'll assume distinct keys.)

Two immediate consequences. First, inorder traversal yields the keys in sorted order — left (all smaller), node, right (all larger), applied recursively. A BST *is* a sorted sequence, stored as a tree. Second, at any node, one comparison eliminates an entire subtree from consideration — the same halving logic as binary search, which is exactly where the name comes from.

         8
        / \
       3   10
      / \    \
     1   6    14
        / \
       4   7

Inorder traversal (left, node, right):
  1, 3, 4, 6, 7, 8, 10, 14  ← always sorted

BST property at every node:
  8 → everything left < 8 (3,1,6,4,7) ✓
      everything right > 8 (10,14)     ✓
  6 → left subtree (4) < 6             ✓
      right subtree (7) > 6            ✓

Search and insert — O(h)

1. search(node, k): if node is null → not found. If k == node.key → found. If k < node.key → search(node.left, k), else search(node.right, k). One comparison per level: O(h).
2. insert(node, k): walk exactly as search would; when you fall off the tree (reach null), attach the new node there. New keys always enter as leaves; no existing node moves. Also O(h).
3. min(node): keep going left until you can't. max: keep going right. Both O(h).

Trace an insert of 4 into the BST {8, 3, 10, 1, 6}: 4 < 8 go left; 4 > 3 go right; 4 < 6 go left; null — attach 4 as 6's left child. Three comparisons, and the invariant holds everywhere by construction: every branch taken was a promise about which subtree 4 belongs in.

Start at root 8:   4 < 8  → go LEFT  to 3
At node 3:         4 > 3  → go RIGHT to 6
At node 6:         4 < 6  → go LEFT  (null!)
                                ↓
Attach 4 as 6's left child:

         8
        / \
       3   10
      / \    \
     1   6    14
        /
       4      ← newly inserted

function insert(node, key):
    if node is null:
        return new Node(key)      // base case: attach here
    if key < node.key:
        node.left  = insert(node.left,  key)
    else if key > node.key:
        node.right = insert(node.right, key)
    // key == node.key → duplicate; ignore or handle per policy
    return node

Deletion — the three cases

Deletion is where BSTs earn their interview reputation, because removing an internal node leaves a hole in the ordering. Three cases, in rising difficulty:

1. Leaf (no children): unlink it from its parent. Done.
2. One child: splice — the parent adopts the node's only child directly (like linked-list deletion). The invariant survives because the whole subtree was already on the correct side.
3. Two children: the node can't just vanish — both subtrees need a new root that keeps the order. Replace the node's key with its inorder successor (the smallest key in its right subtree: one step right, then left all the way down), then delete that successor from the right subtree. The successor is the *least key greater than the deleted one*, so it can sit above both subtrees without breaking any bound — and crucially, the successor itself has at most one child (it has no left child by construction, having been reached by going left to the end), so deleting it lands in case 1 or 2, never recursing into case 3 again.

Before:              After:
       8                    10
      / \                  / \
     3   10               3   14
    / \    \             / \
   1   6    14          1   6
      / \                  / \
     4   7                4   7

Step 1: find inorder successor of 8
        = min of right subtree = 10
Step 2: copy 10 up to root position
Step 3: delete old node 10 from right subtree
        → it has one child (14), so parent adopts 14

Inorder check: 1,3,4,6,7,10,14 ✓

Complexity: it's all about h

Insert 1, 2, 3, 4, 5 in order:

1
 \
  2
   \
    3
     \
      4
       \
        5

Height = n-1 = 4. Every operation is O(n).
This "tree" is just a linked list.

vs balanced form (height = log n = 2):

      3
     / \
    2   4
   /     \
  1       5

The last three rows of the table are the BST's reason to exist — order-aware queries hash tables simply cannot do. But the second column is the catch: every O(log n) claim assumes the tree is bushy. Insert already-sorted keys 1, 2, 3, …, n into a plain BST and each new key goes right of everything: the 'tree' is a linked list, h = n − 1, and every operation is O(n). Sorted or near-sorted input is common in real data (timestamps, IDs), so this isn't a corner case — it's the default failure mode, and it motivates the entire next lesson on self-balancing trees. Space: O(n) all cases, plus O(h) recursion stack for the operations above.

Worked pattern: validating a BST

The interview classic, and a direct test of whether you internalized the invariant. Wrong answer: check node.left.key < node.key < node.right.key at each node — accepts trees where a deep-left descendant of the right subtree violates the grandparent's bound. Right answer: pass range bounds down the recursion.

function isValidBST(node, lo=-∞, hi=+∞):
    if node is null: return true
    if node.key <= lo: return false   // violates lower bound
    if node.key >= hi: return false   // violates upper bound
    return isValidBST(node.left,  lo, node.key) and
           isValidBST(node.right, node.key, hi)

// Initial call:
isValidBST(root, -∞, +∞)

Why the naive "just check children" fails:
        8
       / \
      3   10
           \
            6   ← 6 < 8, violates the root's right-subtree bound!
                  But every parent-child pair looks fine locally.

valid(node, lo, hi): null is valid; node.key must lie strictly inside (lo, hi); recurse left with (lo, node.key) and right with (node.key, hi), starting from (−∞, +∞). Each node is checked against the tightest bound any ancestor imposed — O(n) time, O(h) space. (Equivalent alternative: inorder-traverse and confirm the output is strictly increasing.)

Worked example: range query [4, 9]

Find all keys in [4, 9] in the BST {8, 3, 10, 1, 6, 14, 4, 7}. Start at root 8: 8 is in [4,9] → include it. Then check left (3 < 4, but its right subtree may contain values ≥ 4) and right (10 > 9, but its left subtree may contain values ≤ 9, which is null here). Result: 4, 6, 7, 8. Cost: O(log n + k) where k=4. A hash table would require scanning all 8 keys; the BST prunes whole subtrees.

function rangeQuery(node, lo, hi, results):
    if node is null: return
    if node.key > lo:                     // left subtree may have values >= lo
        rangeQuery(node.left, lo, hi, results)
    if lo <= node.key <= hi:
        results.append(node.key)
    if node.key < hi:                     // right subtree may have values <= hi
        rangeQuery(node.right, lo, hi, results)

Common pitfalls

• Validating parent-child pairs instead of subtree ranges. The signature BST misunderstanding — see above.
• Fumbling two-child deletion. Remember: copy the successor's key up, then delete the successor node (which is guaranteed to be an easy case). Trying to re-wire subtrees directly produces broken trees.
• Feeding sorted input into an unbalanced BST. Instant O(n) degeneration. If input order is untrusted, use a self-balancing variant (next lesson) — which is what library 'sorted map' types are.
• Forgetting duplicates policy. Decide up front: reject, count, or send right — and keep search/insert/delete consistent with it.
• Using a BST when you never need order. If sorted iteration, ranges, and nearest-key queries aren't in your workload, a hash table is simpler and faster. The BST's price (O(log n) everything, balancing complexity) only buys value when order matters.

When to use a BST

• Sorted dynamic data: you need both fast insert/delete and sorted iteration. Sorted arrays can't do both; hash tables can't do sorted.
• Range queries: 'give me everything between A and B' — O(log n + k) on a BST, O(n) on a hash table.
• Floor / ceiling / nearest key: 'what's the biggest key ≤ x?' — direct BST walk.
• Never: when you only need exact lookup with no ordering requirements — a hash table wins O(1) vs O(log n).

Practice problems

1. Kth smallest element in a BST. Inorder traversal emits keys in sorted order. Augment each node with its left-subtree size for an O(log n) solution.
2. Lowest common ancestor (LCA). The LCA of nodes p and q in a BST is the first node where p and q go in different directions. Walk from the root: if both are smaller go left, both larger go right, otherwise the current node is the LCA.
3. Convert sorted array to balanced BST. Recursively pick the middle element as the root, then recurse on left half and right half. Guarantees O(log n) height.

Key takeaways

• One invariant — left subtree smaller, right subtree larger, recursively — creates a searchable sorted structure.
• Search/insert/delete all run in O(h); inorder traversal is sorted order for free.
• Two-child deletion = replace with inorder successor (min of right subtree), then delete the successor from its easy position.
• h is everything: log n when bushy, n when fed sorted input. The unbalanced BST's worst case is common, not exotic.
• Choose BSTs (in balanced form) when you need order — ranges, min/max, successor, sorted scans; choose hash tables when you don't.

The obvious next question: can a tree keep itself bushy no matter what order keys arrive? Yes — AVL and red-black trees, next. Test your deletion-case fluency in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play