leetExpert

Module 18 · BST & Ordered Structures

Practice

Practice~2 min

How to practice this module

BST drills reward the ordering invariant: validation carries bounds, kth-smallest reads inorder, insert and delete are walks, and sorted-array-to-BST balances by mid-splitting. Done when all six show Solved in the hub.

Problems

BST — work them in order; difficulty ascends.

0/6

solved

  1. 1Validate Binary Search TreeMediumBound propagationWatch for: Carry (low, high) down the recursion — comparing only against the parent misses ancestor violations
  2. 2Kth Smallest Element in a BSTMediumInorder countWatch for: Inorder yields sorted order; count down in one pass and stop at zero, or use an explicit stack
  3. 3Lowest Common Ancestor of a BSTMediumProperty-guided walkWatch for: If both values sit on one side, go that way; the first node whose value lies between them is the LCA
  4. 4Insert into a Binary Search TreeMediumLeaf placement walkWatch for: The BST property fixes the insertion point — attach at a null child and return the (possibly new) root
  5. 5Delete Node in a BSTMediumThree-case deleteWatch for: Leaf, one child, two children (replace with the inorder successor) — the two-child case is where people leak the tree
  6. 6Convert Sorted Array to Binary Search TreeEasyMid-split recursionWatch for: Always take the middle element as root so both halves stay balanced; an empty span returns null

Cheatsheet

BST — Left < node < right — search and bounds fall out of the invariant.

Smell → pattern

  • Lookup / insert / delete keyBST walk
  • Ordered traversal neededInorder = sorted
  • Validate BSTCarry (min, max) bounds

Patterns

Search walk

Core

Smell: Find / insert / delete a key

Compare with node; go left or right. Stop at null (miss) or equal (hit). Average O(h).

Inorder stream

Safe

Smell: kth smallest / sorted keys

Inorder yields sorted keys. Use for kth smallest, recover BST from traversal, or validate increasing order.

Bound propagation

Reach

Smell: Validate or search in a range

Each subtree must stay inside (low, high). Tighten the bound when you descend left/right — comparing only to the parent is not enough.

discardkeepmid

Complexity targets

  • Search / insert balanced

    Time
    O(log n)
    Space
    O(1)*
    Note
    *iterative; recursive O(h)

  • Skewed tree worst

    Time
    O(n)
    Space
    O(n)
    Note
    Degenerates to a list

Traps

  • Duplicate policy

    Know whether equals go left, right, or are forbidden. Inconsistent handling breaks validation and delete.

  • Local parent check ≠ BST

    A node can be ≥ parent and still violate an ancestor bound. Propagate (min, max), don’t only compare to parent.