Chapter 10 — Trees & Binary Search Trees

A tree is a linked list where each node can have more than one next pointer.
A BST is a tree where every comparison eliminates half the remaining nodes.

Part 1: Physical Reality — What a Tree Node Is

You already know a linked list node:

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

A binary tree node is identical except it has two next pointers instead of one:

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;   // "next left"
    this.right = null;  // "next right"
  }
}

That's the entire structural difference. Everything trees can do follows from this: the left and right pointers create a branching structure instead of a linear one.

Memory layout:

        [node: val=4, left=→, right=→]
        /                              \
[node: val=2, left=→, right=→]    [node: val=7, left=→, right=→]
      /         \                        /         \
[node:1,→,→] [node:3,→,→]        [node:6,→,→] [node:9,→,→]

Each node is an object somewhere in heap memory. Parent points to children via left/right pointers. There is no parent pointer in a standard binary tree (you'd need a doubly-linked tree for that). This means to access a node's parent, you must traverse from the root.

Part 2: Vocabulary — Terms You Must Know Cold

          4          ← root (the single node with no parent)
        /   \
       2     7       ← internal nodes (have at least one child)
      / \   / \
     1   3 6   9     ← leaves (no children; left=null, right=null)

Height and node count relationship:

For a perfect binary tree of height h: exactly 2^(h+1) - 1 nodes. Height 3 = 15 nodes.

For a degenerate tree (every node has one child — effectively a linked list): n nodes → height n-1 → O(n) operations.

This is why balance matters: the same n nodes can give height O(log n) or O(n) depending on structure. BST operations are O(height) — balanced = fast, degenerate = slow.

Part 3: The BST Property

A Binary Search Tree (BST) adds one invariant to a binary tree:

For every node N: all values in N's left subtree < N.val, and all values in N's right subtree > N.val.

This is recursive — it applies at every node, not just the root.

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

Check: node 3 → left subtree {1} all < 3 ✓. Right subtree {6,4,7} all > 3 ✓.
Check: node 6 → left {4} < 6 ✓. Right {7} > 6 ✓.
Check: node 8 → left {3,1,6,4,7} all < 8 ✓. Right {10,14,13} all > 8 ✓.

The BST property enables O(log n) search: At each node, compare target with node.val. If smaller, go left (eliminate entire right subtree). If larger, go right (eliminate entire left subtree). If equal, found. Same logic as binary search on a sorted array — but encoded in tree structure, enabling O(log n) insert and delete too.

Part 4: Tree Traversals — All Four, with Physical Meaning

There are four fundamental traversal orders. Each visits every node exactly once, giving O(n) time. Space is O(h) for the recursion stack (height of tree).

Inorder (Left → Root → Right)

function inorder(root, result = []) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

Physical meaning: For a BST, inorder traversal produces elements in sorted ascending order. This is not coincidence — it's the BST property made explicit. Left subtree values < root < right subtree values. Inorder visits left first, then root, then right = sorted.

Use for: Extracting sorted values from a BST. "Kth smallest in BST" = stop at kth element in inorder traversal.

Inorder dry run on the tree above:

Visit left of 8 → go to 3.
  Visit left of 3 → go to 1.
    Visit left of 1 → null, return.
    Visit 1.
    Visit right of 1 → null, return.
  Visit 3.
  Visit right of 3 → go to 6.
    Visit left of 6 → go to 4. Visit 4. Left/right null.
    Visit 6.
    Visit right of 6 → go to 7. Visit 7. Left/right null.
Visit 8.
Visit right of 8 → go to 10.
  (similar pattern for 10,13,14)

Result: [1,3,4,6,7,8,10,13,14] ← sorted ✓

Preorder (Root → Left → Right)

function preorder(root, result = []) {
  if (!root) return result;
  result.push(root.val);      // visit root FIRST
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

Physical meaning: You encounter each node before its children. This is the order in which you'd serialize or copy a tree — the root tells you the structure before you know the children.

Use for: Serialization (save tree to disk), creating a copy of a tree, printing directory trees.

Result on example: [8,3,1,6,4,7,10,14,13]

Postorder (Left → Right → Root)

function postorder(root, result = []) {
  if (!root) return result;
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.val);      // visit root LAST
  return result;
}

Physical meaning: You process children before the parent. This is the order for deleting a tree (delete children before parent — if you deleted parent first, you'd lose the pointers to children), evaluating expression trees (evaluate operands before applying operator), or computing subtree properties (subtree heights, subtree sums).

Use for: Memory cleanup, expression tree evaluation, computing values that depend on children's results.

Result on example: [1,4,7,6,3,13,14,10,8]

Level Order / BFS (Level by Level)

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Physical meaning: Process all nodes at depth d before any node at depth d+1. Uses a queue (FIFO) from Chapter 7.

Result on example: [[8],[3,10],[1,6,14],[4,7,13]]

Traversal choice guide:

• Need sorted values from BST → inorder.
• Need to serialize/copy → preorder.
• Need to process children before parent → postorder.
• Need level-by-level, shortest path, minimum depth → level order (BFS).

Part 5: BST Operations

Search — O(h)

function searchBST(root, target) {
  if (!root) return null;
  if (root.val === target) return root;
  if (target < root.val) return searchBST(root.left, target);
  return searchBST(root.right, target);
}

At each node, one subtree is eliminated. O(h) where h = height. If balanced: O(log n). If degenerate: O(n).

Insert — O(h)

function insertBST(root, val) {
  if (!root) return new TreeNode(val);  // found insertion point
  if (val < root.val) root.left = insertBST(root.left, val);
  else if (val > root.val) root.right = insertBST(root.right, val);
  // val === root.val: already exists, do nothing (or update)
  return root;
}

Follow the search path. Insert at the first null position you encounter. The recursive structure: root.left = insertBST(root.left, val) means "the result of inserting val into the left subtree becomes the new left child." When root is null, we've found the leaf position.

Dry run: insertBST(root, 5) into the example tree

root.val=8, 5<8 → go left. root.left = insertBST(node(3), 5).
  root.val=3, 5>3 → go right. root.right = insertBST(node(6), 5).
    root.val=6, 5<6 → go left. root.left = insertBST(node(4), 5).
      root.val=4, 5>4 → go right. root.right = insertBST(null, 5).
        root is null → return new TreeNode(5).
      node(4).right = node(5). return node(4).
    node(6).left = node(4) (with 5 as its right child). return node(6).
  node(3).right = node(6). return node(3).
node(8).left = node(3). return node(8).

Node 5 inserted between 4 and 6. BST property maintained. ✓

Delete — O(h), Three Cases

Deletion is the hardest BST operation. Find the node, then handle three cases:

Case 1: Node is a leaf. Just return null (remove it).

Case 2: Node has one child. Return that child (bypass the node).

Case 3: Node has two children. Find the inorder successor (smallest value in the right subtree — leftmost node of right subtree). Copy its value into the current node. Delete the inorder successor (which has at most one child — no left child, since it's leftmost).

function deleteNode(root, key) {
  if (!root) return null;

  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    // Found the node to delete
    if (!root.left) return root.right;   // Case 1 or 2: no left child
    if (!root.right) return root.left;   // Case 2: no right child

    // Case 3: two children
    // Find inorder successor (min of right subtree)
    let successor = root.right;
    while (successor.left) successor = successor.left;

    root.val = successor.val;                        // copy successor's value
    root.right = deleteNode(root.right, successor.val); // delete successor
  }

  return root;
}

Why inorder successor? We need a replacement value that maintains the BST property. The inorder successor is the smallest value greater than the deleted node's value — it can replace the node without violating the BST property (it's larger than everything in the left subtree and smaller than everything else in the right subtree).

Part 6: Height, Balance, and Why It Matters

Height computation:

function height(root) {
  if (!root) return -1;  // null node has height -1; leaf has height 0
  return 1 + Math.max(height(root.left), height(root.right));
}

Postorder traversal — compute children first, then use their heights.

The balance problem:

Insert [1, 2, 3, 4, 5] into a BST in order:

1
 \
  2
   \
    3
     \
      4
       \
        5

Height = 4 (for n=5). This is a degenerate tree — a linked list. Every BST operation is O(n).

Insert [3, 1, 5, 2, 4] into a BST:

    3
   / \
  1   5
   \ /
   2 4

Height = 2. O(log n) operations.

Same values, different insertion order → different heights. The BST property doesn't prevent degeneration. This is why self-balancing BSTs exist.

AVL Trees: After every insert/delete, check if any node's balance factor (left height − right height) exceeds ±1. If so, perform rotations to restore balance. Guarantee O(log n) height at all times.

Red-Black Trees: Looser balance (height ≤ 2 log n) but fewer rotations per operation. Used in most production implementations: Java's TreeMap/TreeSet, C++ std::map/std::set, Linux kernel's completely fair scheduler.

For interviews, you won't implement AVL or Red-Black trees from scratch. But you should know why they exist and that JavaScript's V8 engine uses Red-Black trees for its Map and Set implementations.

Part 7: Important Tree Properties — Deriving Answers

Many tree problems ask for properties that are naturally computed via recursion. The pattern:

function property(node):
  if node is null: return base case value
  left = property(node.left)   ← recursive leap of faith
  right = property(node.right)
  return combine(node.val, left, right)

Maximum depth:

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Subtree sum:

function subtreeSum(root) {
  if (!root) return 0;
  return root.val + subtreeSum(root.left) + subtreeSum(root.right);
}

Diameter (longest path between any two nodes):

The diameter passes through some "highest" node that acts as the apex. At each node, the diameter through it = height(left) + height(right) + 2. We want the max across all nodes.

function diameterOfBinaryTree(root) {
  let maxDiam = 0;

  function height(node) {
    if (!node) return -1;
    const lh = height(node.left);
    const rh = height(node.right);
    maxDiam = Math.max(maxDiam, lh + rh + 2);  // diameter through this node
    return 1 + Math.max(lh, rh);
  }

  height(root);
  return maxDiam;
}

This is the postorder pattern: compute subtree property (height), use it to update a global answer (max diameter), return the property to the parent.

Part 8: Lowest Common Ancestor (LCA)

Problem: Find the lowest common ancestor of two nodes p and q in a binary tree.

The LCA is the deepest node that has both p and q as descendants (a node is a descendant of itself).

Recursive insight:

• If the current node is null → return null (neither p nor q here).
• If the current node is p or q → return the current node (found one; the other must be in a subtree).
• Recurse left and right.
  • If both sides return non-null → current node is the LCA (p is on one side, q is on the other).
  • If only one side returns non-null → that side contains both p and q; pass it up.

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;  // p on left, q on right → root is LCA
  return left || right;             // both in same subtree
}

Dry run — tree [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1:

LCA(3, 5, 1):
  LCA(5, 5, 1): root===p=5 → return node(5).
  LCA(1, 5, 1): root===q=1 → return node(1).
  left=node(5), right=node(1). Both non-null → return root=node(3).

Dry run — same tree, p=5, q=4:

LCA(3, 5, 4):
  LCA(5, 5, 4): root===p=5 → return node(5).
  LCA(1, 5, 4): left=LCA(0,5,4)=null. right=LCA(8,5,4)=null. return null.
  left=node(5), right=null → return node(5).

Both p=5 and q=4 are in the left subtree of 3. The LCA is 5 (which is an ancestor of 4 through the path 5→2→4).

Complexity: O(n) time (visits every node once in worst case). O(h) space.

Part 9: Validate BST

Problem: Determine if a binary tree is a valid BST.

The naive approach — check node.left.val < node.val < node.right.val at each node — fails:

    5
   / \
  1   4
     / \
    3   6

Node 4 passes the local check (3 < 4 < 6) but the tree is invalid: 4 is in the right subtree of 5, but 4 < 5. The constraint isn't just "left child < parent" — it's "entire left subtree < parent."

Correct approach: Pass valid min/max bounds down the tree. Every node must satisfy min < node.val < max.

function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) &&   // left subtree: max = current val
         isValidBST(root.right, root.val, max);     // right subtree: min = current val
}

Dry run on invalid tree above:

isValidBST(5, -∞, ∞):
  5 in (-∞, ∞) ✓.
  isValidBST(1, -∞, 5): 1 in (-∞,5) ✓. Both children null → true.
  isValidBST(4, 5, ∞):
    4 <= 5. ← Fails! return false.
  false && anything → false. return false. ✓

The min/max bounds propagate the constraint: going right from node 5 means everything in that subtree must be > 5. When we reach node 4, we check 4 > 5 — false. Invalid. ✓

Part 10: Mental Model — Tree Problem Patterns

Pattern 1: Compute property bottom-up (postorder)

Need subtree heights, subtree sums, balance check? Compute children first, then combine. Template: function f(node) { left = f(node.left); right = f(node.right); return combine; }

Pattern 2: Pass constraints top-down (preorder)

Need to validate BST, check node visibility, count paths? Pass accumulated state down. Template: function f(node, state) { if (!node) return base; return f(node.left, newState) && f(node.right, newState); }

Pattern 3: Find a specific path or node (inorder for BST)

Kth smallest, closest value, range queries on BST? Use inorder — it gives sorted order.

Pattern 4: Level-by-level (BFS)

Minimum depth, zigzag traversal, right side view? Use queue-based BFS.

Pattern 5: Update parent from child (postorder with return)

LCA, path sum, diameter, max path sum? Process children, return result up to parent, update global.

When to use what:

Part 11: Real Systems

DOM Tree:
Every HTML page is a tree. <html> is the root. <head> and <body> are children. Every element has children and a parent. The browser's layout engine traverses this tree — preorder for initial rendering (paint parent before children), postorder for layout calculations (children determine parent's height in certain flex/grid scenarios). document.querySelector does DFS on the DOM tree. querySelectorAll does preorder DFS and collects all matches.

React Component Tree:
React's reconciler (Fiber, discussed in Chapter 4) represents the component tree as a linked list of fiber nodes (each fiber has child, sibling, return pointers — not a standard binary tree but a tree). React's diffing algorithm traverses this tree to find what changed. React.createContext and useContext search up the component tree for the nearest provider — ancestor search, O(depth).

PostgreSQL B-Tree Indexes:
From Chapter 9: B-trees are n-ary trees where each node stores sorted keys. Internal nodes have keys to navigate; leaf nodes have the actual values. The tree is always balanced (same height from root to every leaf) because B-trees rebalance on insert by splitting nodes. This guarantees O(log n) operations regardless of insertion order — unlike unbalanced BSTs.

V8 — JavaScript Object Hidden Classes:
V8 internally assigns "hidden classes" (also called "shapes" or "maps") to JavaScript objects. When you add a property to an object, V8 creates a new hidden class that extends the previous one. These form a tree — each hidden class knows its parent. V8 uses this tree to JIT-compile efficient property access (polymorphic inline caches). When two objects share the same hidden class tree path, their property accesses are compiled to identical machine code.

File System (ext4, NTFS, APFS):
Directory structures are trees. / is the root. Each directory is an internal node. Files are leaves. File system traversal (like find command or fs.readdir recursively) is tree traversal. Inodes in ext4 store a B-tree of block pointers for large files — a tree within a tree.

Huffman Coding (Compression):
Gzip, zlib, and DEFLATE (used in HTTP compression and PNG) use Huffman trees. The most frequent characters get the shortest codes. Building the Huffman tree: a bottom-up process where you merge the two smallest-frequency nodes at each step (a priority queue of leaf nodes, building a binary tree). The tree structure encodes the compression scheme. This is postorder construction — leaves first, root last.

Part 12: Vocabulary Map

Part 13: 5 Practice Problems

1. Trace and Predict

function f(root) {
  if (!root) return 0;
  const left = f(root.left);
  const right = f(root.right);
  if (left === -1 || right === -1 || Math.abs(left - right) > 1) return -1;
  return 1 + Math.max(left, right);
}

Trace on a balanced tree [3,9,20,null,null,15,7] and on an unbalanced tree [1,2,2,3,3,null,null,4,4]. What does -1 signify? What does this function check? (LeetCode 110.)

2. Find the Waste

Computing diameter naively: for each node, compute height(left) + height(right) + 2. If height is computed separately for each node: O(n²) total (recomputing subtree heights repeatedly).

The diameterOfBinaryTree in Part 7 avoids this by computing height and updating diameter in a single postorder pass. Trace it on [1,2,3,4,5]. At each node, what is the height returned? What is maxDiam at each node?

3. Failure Analysis

function isValidBST(root) {
  if (!root) return true;
  if (root.left && root.left.val >= root.val) return false;
  if (root.right && root.right.val <= root.val) return false;
  return isValidBST(root.left) && isValidBST(root.right);
}

Provide a specific tree that is NOT a valid BST but passes this check. Then explain why the correct fix is to pass min/max bounds.

4. Design Under Constraints

Design kthSmallest(root, k) (LeetCode 230): find the kth smallest element in a BST without converting to an array.

Two approaches:

• Recursive inorder: elegant but uses O(h) stack space and can't stop early without throwing an exception.
• Iterative inorder with explicit stack: can stop as soon as the kth element is found.

Write the iterative inorder approach. What is the time complexity? What is the space complexity? When is the iterative version strictly better?

5. Reach Beyond

Design serialize(root) and deserialize(data) (LeetCode 297 — Hard): convert a binary tree to a string and back.

Constraint: must reconstruct the exact tree (not just a BST-equivalent). This means preorder traversal with null markers.

serialize outputs: "1,2,null,null,3,4,null,null,5,null,null" for a specific tree.

deserialize splits by comma, uses a queue or index pointer to rebuild. The key insight: preorder traversal naturally encodes the structure — the root always comes first, then left subtree, then right subtree. Write both functions. What differentiates this from inorder serialization (which is ambiguous for reconstructing the tree)?

Connect Forward

Chapter 11 — Backtracking uses trees implicitly. The recursive "decision tree" we drew for subsets in Chapter 4a is a literal tree. Backtracking algorithms traverse this decision tree in DFS order (preorder), pruning branches that violate constraints.

Chapter 12 — Graphs generalizes trees: a tree is an acyclic connected graph. Graph BFS uses a queue (same as level-order tree traversal). Graph DFS uses a stack or recursion (same as tree DFS).

Chapter 13 — Dynamic Programming will use trees in problems like "house robber on a binary tree" and "maximum path sum" — both use the postorder pattern of computing subtree values and combining them.

Connect Backward

Chapter 4 (Recursion) is the entire foundation. Every tree traversal is recursion. The recursive leap of faith: when you write height(root.left), you trust it returns the correct height without tracing all the way down. Chapter 4's framework — base case, recursive case, return value — is the exact structure of every tree function.

Chapter 7 (Stack & Queue): iterative DFS on trees uses an explicit stack (same as the call stack, made visible). Level-order traversal uses a queue. Chapter 9 (Binary Search): BST search is binary search on a sorted data structure. Every BST operation is O(log n) for the same reason binary search is O(log n) — eliminating half the possibilities at each step.