Level 2 · 40 min

Trees & BSTs: Structure-Driven Algorithms

Binary trees and binary search trees (BSTs) are the workhorses of structured search. CLRS chapter 12 develops the BST; Cracking the Coding Interview chapter 4 contains the exhaustive interview taxonomy: traversals, validation, balancing checks, and lowest common ancestor.

Traversal Orders and What They Compute

Four traversals: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root), and level-order (BFS). Each computes a different thing: preorder reproduces the tree from a serialization (with null markers); inorder of a BST yields keys in sorted order — the BST''s defining property; postorder is used when children must be computed before parents (e.g. tree height, memory cleanup); level-order is BFS, used for shortest-path-in-tree and zigzag patterns. Recursive implementations are 4-line; iterative versions need an explicit stack (preorder/inorder/postorder) or queue (level). CLRS exercise 12.1-3 covers iterative inorder using parent pointers; without parent pointers you need a stack.

BST Invariant and Operations

BST invariant: for every node, all keys in the left subtree are less, all in the right are greater. Search, insert, delete: O(h) where h is the height — O(log n) for balanced, O(n) worst-case for skewed (insertion of sorted input creates a linked list). Validation pitfall: checking only ''left.val < node.val < right.val'' is wrong — must check the global bound, not just local. Pass min/max bounds down the recursion. Delete is the tricky operation: leaf (just remove), one child (splice in child), two children (find inorder successor, swap, delete successor). CLRS Theorem 12.4: average-case BST height for random insertion is O(log n), but adversarial input (sorted) produces O(n). This is why production trees are self-balancing.

Balancing: AVL, Red-Black, and Why It Matters

Self-balancing trees guarantee O(log n) height regardless of insertion order. AVL: rotation on imbalance > 1 between subtrees; tighter balance, more rotations. Red-black: looser balance constraints, fewer rotations on insert/delete — Java''s TreeMap, C++''s std::map use red-black. Both store one extra bit per node. CLRS chapter 13 derives the red-black height bound: at most 2·log(n+1). Practical guidance: read-heavy workloads → AVL (tighter balance, faster lookups); write-heavy → red-black (fewer rebalance ops). For very write-heavy: B-trees (on disk) or skip lists (in memory) reduce constants. Java TreeSet and TreeMap are the obvious in-process choices when sorted iteration is needed alongside O(log n) lookups.

Key Takeaways

Inorder traversal of a BST yields sorted keys — this is the operational definition.
Validate a BST with global bounds (min/max) recursively, not local left.val < node.val < right.val.
Worst-case BST height is O(n) for sorted insertion. Use TreeMap/TreeSet (red-black) or AVL for guaranteed O(log n).

Code example

// Java — validate BST with global bounds
static boolean isBST(TreeNode root) {
  return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
static boolean check(TreeNode n, long lo, long hi) {
  if (n == null) return true;
  if (n.val <= lo || n.val >= hi) return false;
  return check(n.left, lo, n.val) '&'&' check(n.right, n.val, hi);
}

// Iterative inorder using explicit stack
static List<Integer> inorder(TreeNode root) {
  List<Integer> result = new ArrayList<'>();
  Deque<TreeNode> stack = new ArrayDeque<'>();
  TreeNode curr = root;
  while (curr != null || !stack.isEmpty()) {
    while (curr != null) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.add(curr.val);
    curr = curr.right;
  }
  return result;
}