🌳 Trees & BST

A learning sheet — trees are recursion made visible. Master one question — "what does each call return to its parent?" — and most tree problems fall in three lines.

🧠 1 · How to think — the return-value contract

A binary tree node is { val, left, right }. Almost every solution is one recursive function over subtrees. The skill that unlocks all of them is being ruthlessly clear about the contract of your recursion. Before writing a line, answer three questions:

The single biggest tree confusion is mixing up what you return (one value, for the parent to keep recursing) with what you record (a global "best", which may use both children at once). Diameter is the perfect teacher.

Watch it get invented — Diameter of a Binary Tree

1. Warm-up: height. height(node) RETURNS the node-count of the tallest path down. Base: height(null) = 0. Combine: 1 + max(height(left), height(right)).
2. The twist. The diameter (longest path between any two nodes) bends at some node and uses both sides: leftHeight + rightHeight. But the parent can't use a "bent" length — it needs a straight height. So dfs must RETURN the height while RECORDING left + right into a global.
3. Payoff. One O(n) pass; the global holds the answer even though the function returns something else.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The six core patterns

Node shape: class TreeNode { val: number; left: TreeNode|null; right: TreeNode|null }. Each: a one-liner, a 🔑 invariant, a template, a 🎤 interview lens.

4.1 · Traversals (DFS & BFS)

“Pre = me-first, In = left-me-right (sorted for a BST), Post = children-first; BFS = a queue.”

Start with the simplest thing that works — recursion. All three depth-first orders are the same code; only where you place the visit relative to the two calls changes — see it at a glance:

if (!n) return;
push(n.val);
go(n.left);
go(n.right);

if (!n) return;
go(n.left);
push(n.val);
go(n.right);

if (!n) return;
go(n.left);
go(n.right);
push(n.val);

Same skeleton — only the highlighted visit line moves.

// Recursive DFS — identical shape; only the line that "visits" moves
function preorder(node: TreeNode | null, out: number[] = []): number[] {
  if (!node) return out;
  out.push(node.val);                 // visit FIRST   → PREORDER  (node, L, R)
  preorder(node.left, out);
  preorder(node.right, out);
  return out;
}
function inorder(node: TreeNode | null, out: number[] = []): number[] {
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.val);                 // visit BETWEEN → INORDER   (L, node, R) — sorted in a BST
  inorder(node.right, out);
  return out;
}
function postorder(node: TreeNode | null, out: number[] = []): number[] {
  if (!node) return out;
  postorder(node.left, out);
  postorder(node.right, out);
  out.push(node.val);                 // visit LAST    → POSTORDER (L, R, node) — the basis of §4.2
  return out;
}

Now all three iteratively — an explicit stack replaces the call stack, plus BFS with a queue. Postorder comes in two forms; the note after the code says when to reach for each:

// Iterative INORDER — push the left spine, pop, go right
function inorderIter(root: TreeNode | null): number[] {
  const out: number[] = [], st: TreeNode[] = []; let cur = root;
  while (cur || st.length) {
    while (cur) { st.push(cur); cur = cur.left; }   // dive left
    cur = st.pop()!; out.push(cur.val);             // visit
    cur = cur.right;                                // then right
  }
  return out;
}

// Iterative PREORDER — stack; push right BEFORE left so left pops first
function preorderIter(root: TreeNode | null): number[] {
  if (!root) return [];
  const out: number[] = [], st: TreeNode[] = [root];
  while (st.length) {
    const n = st.pop()!; out.push(n.val);           // visit on pop
    if (n.right) st.push(n.right);
    if (n.left)  st.push(n.left);
  }
  return out;
}

// Iterative POSTORDER (values only) — a preorder variant (node, right, left), then reversed
function postorderIter(root: TreeNode | null): number[] {
  if (!root) return [];
  const out: number[] = [], st: TreeNode[] = [root];
  while (st.length) {
    const n = st.pop()!; out.unshift(n.val);        // push to the FRONT = reverse at the end
    if (n.left)  st.push(n.left);
    if (n.right) st.push(n.right);
  }
  return out;
}

// Iterative POSTORDER (genuine) — mark a node "visited" on the stack; process it on the 2nd pop
function postorderIterVisited(root: TreeNode | null): number[] {
  if (!root) return [];
  const out: number[] = [];
  const st: [TreeNode, boolean][] = [[root, false]];   // each entry: [node, seenBefore?]
  while (st.length) {
    const [node, visited] = st.pop()!;
    if (visited) {
      out.push(node.val);                // 2nd pop → children already done → visit now
    } else {
      st.push([node, true]);             // re-push marked, to return AFTER the children
      if (node.right) st.push([node.right, false]);   // push right then left,
      if (node.left)  st.push([node.left, false]);    // so left is popped (and finished) first
    }
  }
  return out;
}

// BFS level order — a queue, one level per outer iteration
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const out: number[][] = [];
  let q: TreeNode[] = [root];
  while (q.length) {
    const level: number[] = [], next: TreeNode[] = [];
    for (const x of q) {
      level.push(x.val);
      if (x.left) next.push(x.left);
      if (x.right) next.push(x.right);
    }
    out.push(level);
    q = next;
  }
  return out;
}

// Right Side View (199) — level order, keep only the LAST value of each level
function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const out: number[] = [];
  const q: TreeNode[] = [root];
  let front = 0;
  while (front < q.length) {
    const levelEnd = q.length;           // this level's boundary
    while (front < levelEnd) {
      const node = q[front++];
      if (front === levelEnd) out.push(node.val);   // last node of the level
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
  }
  return out;
}

// Zigzag (103) — level order + a direction flag; reverse alternate levels
function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const out: number[][] = [];
  const q: TreeNode[] = [root];
  let front = 0;
  let leftToRight = true;
  while (front < q.length) {
    const level: number[] = [];
    const levelEnd = q.length;
    while (front < levelEnd) {
      const node = q[front++];
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    if (!leftToRight) level.reverse();
    out.push(level);
    leftToRight = !leftToRight;
  }
  return out;
}

// Vertical Order (314) — BFS carrying a column index; group values by column
function verticalOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const cols = new Map<number, number[]>();   // column → values (BFS order = top-down, ties L→R)
  const q: [TreeNode, number][] = [[root, 0]];
  let front = 0;
  let minCol = 0, maxCol = 0;
  while (front < q.length) {
    const [node, col] = q[front++];
    if (!cols.has(col)) cols.set(col, []);
    cols.get(col)!.push(node.val);
    minCol = Math.min(minCol, col);
    maxCol = Math.max(maxCol, col);
    if (node.left) q.push([node.left, col - 1]);
    if (node.right) q.push([node.right, col + 1]);
  }
  const out: number[][] = [];
  for (let c = minCol; c <= maxCol; c++) out.push(cols.get(c)!);
  return out;
}

// Morris inorder — O(1) space: thread each node to its inorder predecessor, then unthread
function morrisInorder(root: TreeNode | null): number[] {
  const out: number[] = [];
  let cur = root;
  while (cur) {
    if (!cur.left) {                                  // no left subtree → visit, then go right
      out.push(cur.val);
      cur = cur.right;
    } else {
      let pred = cur.left;                            // predecessor = rightmost node of the left subtree
      while (pred.right && pred.right !== cur) pred = pred.right;
      if (!pred.right) {                              // first visit → thread the breadcrumb back to cur
        pred.right = cur;
        cur = cur.left;
      } else {                                        // thread already set → left subtree done; unwire + visit
        pred.right = null;
        out.push(cur.val);
        cur = cur.right;
      }
    }
  }
  return out;
}

4.2 · Return-value DFS (the heart)

“Compute children first, fold their returns into yours — and record a global if the answer bends.”

Setup: this is the org-chart manager made concrete. State the contract, then the body is literally three lines: (1) BASE — what does an empty subtree (null) report? (2) COMBINE — ask both children, fold their returns L and R into your answer. (3) RETURN / RECORD — hand one summary up, and if the answer can bend here, also write it to a global. Below, the same dfs three ways, each one twist harder: diameter (return-vs-record), balanced (height hijacked by a -1 "failed" sentinel), and the hardest, Max Path Sum.

// Diameter — RETURN height, RECORD the bending path
function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;
  function height(node: TreeNode | null): number {   // CONTRACT: height of this subtree
    if (!node) return 0;                              // base case
    const L = height(node.left);
    const R = height(node.right);
    best = Math.max(best, L + R);                     // RECORD: path bending at node
    return 1 + Math.max(L, R);                        // RETURN: straight height for parent
  }
  height(root);
  return best;
}

// Balanced? — RETURN height, but hijack it with -1 as a "subtree already failed" sentinel
function isBalanced(root: TreeNode | null): boolean {
  function height(node: TreeNode | null): number {   // CONTRACT: height, or -1 if unbalanced below
    if (!node) return 0;
    const L = height(node.left);
    if (L === -1) return -1;              // a subtree already failed → propagate -1 up
    const R = height(node.right);
    if (R === -1) return -1;
    if (Math.abs(L - R) > 1) return -1;   // imbalance detected here → fail
    return 1 + Math.max(L, R);
  }
  return height(root) !== -1;
}

// Max Path Sum — clamp negative branches; RETURN a straight path, RECORD a bent one
function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  function gain(node: TreeNode | null): number {      // CONTRACT: best downward path sum from node
    if (!node) return 0;
    const L = Math.max(0, gain(node.left));           // ignore a negative branch
    const R = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + L + R);          // RECORD: path that bends here
    return node.val + Math.max(L, R);                 // RETURN: straight path down
  }
  gain(root);
  return best;
}

// Count Complete Tree Nodes (222) — spot perfect subtrees by their edge heights
function countNodes(root: TreeNode | null): number {
  if (!root) return 0;
  let lh = 1;
  let l = root.left;
  while (l) { lh++; l = l.left; }        // depth hugging the LEFT edge
  let rh = 1;
  let r = root.right;
  while (r) { rh++; r = r.right; }       // depth hugging the RIGHT edge
  if (lh === rh) return (1 << lh) - 1;   // equal → perfect tree → 2^h − 1, done in O(1)
  const L = countNodes(root.left);       // not perfect → recurse; one side always IS perfect,
  const R = countNodes(root.right);      // so only one real branch survives per level
  return 1 + L + R;
}

// 1110 Delete Nodes and Return Forest — return node-or-null, parent re-links
function delNodes(root: TreeNode | null, toDelete: number[]): TreeNode[] {
  const del = new Set(toDelete);
  const forest: TreeNode[] = [];
  function dfs(node: TreeNode | null, isRoot: boolean): TreeNode | null {
    if (!node) return null;
    const gone = del.has(node.val);
    if (isRoot && !gone) forest.push(node);   // my parent was deleted (or I'm the root) → I start a new tree
    node.left = dfs(node.left, gone);         // the RETURN re-links (or cuts) the child
    node.right = dfs(node.right, gone);
    return gone ? null : node;
  }
  dfs(root, true);
  return forest;
}

// 979 Distribute Coins — return the net balance, record moves on each edge
function distributeCoins(root: TreeNode | null): number {
  let moves = 0;
  function dfs(n: TreeNode | null): number {  // + = surplus to send up, - = coins needed from above
    if (!n) return 0;
    const l = dfs(n.left), r = dfs(n.right);
    moves += Math.abs(l) + Math.abs(r);       // every unit crossing an edge costs exactly one move
    return n.val + l + r - 1;                 // keep one coin for myself
  }
  dfs(root);
  return moves;
}

// 968 Binary Tree Cameras — greedy post-order, 3 states
function minCameraCover(root: TreeNode | null): number {
  let cams = 0;
  function dfs(n: TreeNode | null): 0 | 1 | 2 {   // 0 = not covered · 1 = has camera · 2 = covered, no camera
    if (!n) return 2;                             // null needs nothing → counts as covered
    const l = dfs(n.left), r = dfs(n.right);
    if (l === 0 || r === 0) { cams++; return 1; }  // a child is uncovered → I MUST hold a camera
    if (l === 1 || r === 1) return 2;              // a child's camera covers me
    return 0;                                      // nothing nearby → ask my parent
  }
  if (dfs(root) === 0) cams++;                     // root ended uncovered → one more camera
  return cams;
}

4.3 · BST = ordered

“Left < node < right — so search is binary, and inorder is sorted.”

Setup: a plain tree can force you to check every node — O(n). A BST is binary search frozen into a data structure: because left < node < right, one comparison tells you which half to keep and which to throw away — exactly like guessing a number in 1–100 with "higher / lower" hints. So you walk a single root-to-leaf path instead of the whole tree: O(h), and h ≈ log n when balanced. Two facts do everything: you navigate by comparison (that's the binary search), and an inorder walk emits values in sorted order.

Navigate — O(h), one comparison per step (this is the binary search).

// Search (700) — walk by comparison
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  while (root) {
    if (root.val === val) return root;
    if (val < root.val) root = root.left;    // smaller → go left
    else root = root.right;                  // bigger → go right
  }
  return null;
}

// LCA in a BST (235) — the split point where the two values diverge
function lcaBST(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  let node = root;
  while (node) {
    if (p.val < node.val && q.val < node.val) node = node.left;        // both smaller → left
    else if (p.val > node.val && q.val > node.val) node = node.right;  // both bigger → right
    else return node;                                                  // they split here → LCA
  }
  return null;
}

// Inorder successor (285) — smallest node greater than p
function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
  let succ: TreeNode | null = null;
  let cur = root;
  while (cur) {
    if (p.val < cur.val) {
      succ = cur;          // candidate; a smaller one may be further left
      cur = cur.left;
    } else {
      cur = cur.right;     // p.val >= cur.val → successor is further right
    }
  }
  return succ;
}

Validate & k-th — both lean on "an inorder walk of a BST is sorted."

// Validate (98) — recursive: carry the allowed (lo, hi) range down
function isValidBST(node: TreeNode | null, lo = -Infinity, hi = Infinity): boolean {
  if (!node) return true;
  if (node.val <= lo || node.val >= hi) return false;
  const L = isValidBST(node.left, lo, node.val);
  const R = isValidBST(node.right, node.val, hi);
  return L && R;
}

// Validate (98) — iterative: an inorder walk must be strictly increasing
function isValidBSTIter(root: TreeNode | null): boolean {
  const st: TreeNode[] = []; let cur = root, prev = -Infinity;
  while (cur || st.length) {
    while (cur) { st.push(cur); cur = cur.left; }
    cur = st.pop()!;
    if (cur.val <= prev) return false;   // not strictly increasing → invalid
    prev = cur.val;
    cur = cur.right;
  }
  return true;
}

// k-th smallest (230) — inorder yields sorted order; stop at the k-th
function kthSmallest(root: TreeNode | null, k: number): number {
  const st: TreeNode[] = []; let cur = root;
  while (cur || st.length) {
    while (cur) { st.push(cur); cur = cur.left; }
    cur = st.pop()!;
    if (--k === 0) return cur.val;
    cur = cur.right;
  }
  return -1;
}

Iterate on demand — kthSmallest generalized into an API. Same stack machinery, paused between calls; the classic "what if it's called repeatedly?" follow-up.

// BST Iterator (173) — controlled inorder walk; next() is amortized O(1), space O(h)
class BSTIterator {
  private st: TreeNode[] = [];
  constructor(root: TreeNode | null) {
    this.pushLeft(root);                 // stage the smallest: the left spine
  }
  private pushLeft(node: TreeNode | null): void {
    while (node) {
      this.st.push(node);
      node = node.left;
    }
  }
  next(): number {
    const node = this.st.pop()!;         // smallest unseen value
    this.pushLeft(node.right);           // stage its right subtree's left spine
    return node.val;
  }
  hasNext(): boolean {
    return this.st.length > 0;
  }
}

Insert — recursive and iterative both just walk to the empty slot and attach.

// Insert (701) — recursive: hang the new node where the walk falls off
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insertIntoBST(root.left, val);
  else root.right = insertIntoBST(root.right, val);
  return root;
}

// Insert (701) — iterative: remember the parent, then attach
function insertIntoBSTIter(root: TreeNode | null, val: number): TreeNode | null {
  const node = new TreeNode(val);
  if (!root) return node;
  let cur: TreeNode | null = root, parent: TreeNode = root;
  while (cur) {
    parent = cur;
    if (val < cur.val) cur = cur.left;
    else cur = cur.right;
  }
  if (val < parent.val) parent.left = node;
  else parent.right = node;
  return root;
}

// Delete (450) — 3 cases; two children → replace with inorder successor
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  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;     // 0 or 1 child → splice past it
    if (!root.right) return root.left;
    let succ = root.right;                 // 2 children → inorder successor
    while (succ.left) succ = succ.left;    // (smallest in the right subtree)
    root.val = succ.val;                   // copy its value up
    root.right = deleteNode(root.right, succ.val);   // then delete the successor
  }
  return root;
}

4.4 · LCA & paths — postorder bubble-up

“If p and q surface from different children, you're standing on their ancestor.”

Setup: "LCA" is literally lowest common ancestor — picture two people tracing their family trees upward; the first ancestor they share is the answer. The code finds that merge point by asking each subtree "is p or q below you?": the node that hears "yes" from both sides is where their two paths first meet. Everything bubbles up from the leaves (postorder).

// LCA in a general binary tree
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || root === p || root === q) return root;   // found one (or hit bottom)
  const L = lowestCommonAncestor(root.left, p, q);
  const R = lowestCommonAncestor(root.right, p, q);
  if (L && R) return root;        // p and q on different sides → this is the LCA
  return L ?? R;                  // both on one side (or neither) → pass it up
}

// Path Sum III (437) — count downward paths (any start node) summing to target
function pathSumIII(root: TreeNode | null, targetSum: number): number {
  const prefix = new Map<number, number>();    // running-sum → how many ancestors have it
  prefix.set(0, 1);                            // empty prefix = "path starts at the root"
  let count = 0;
  function dfs(node: TreeNode | null, running: number): void {
    if (!node) return;
    running += node.val;
    count += prefix.get(running - targetSum) ?? 0;         // each match = a valid start point
    prefix.set(running, (prefix.get(running) ?? 0) + 1);   // add myself for my descendants
    dfs(node.left, running);
    dfs(node.right, running);
    prefix.set(running, prefix.get(running)! - 1);         // BACKTRACK — leave the path clean
  }
  dfs(root, 0);
  return count;
}

4.5 · Construct & serialize

“Preorder hands you the root; inorder tells you where left ends and right begins.”

Setup: building a tree is recursion in reverse — identify the root, split the remaining nodes into left/right groups, recurse. Serialization is just a preorder walk with explicit null markers.

// Build a tree from preorder + inorder
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const pos = new Map(inorder.map((v, i) => [v, i]));
  let p = 0;
  function build(lo: number, hi: number): TreeNode | null {
    if (lo > hi) return null;
    const node = new TreeNode(preorder[p++]);   // preorder front = root
    const mid = pos.get(node.val)!;             // its index in inorder splits L | R
    node.left = build(lo, mid - 1);
    node.right = build(mid + 1, hi);
    return node;
  }
  return build(0, inorder.length - 1);
}

// Serialize / deserialize (preorder with '#' for null)
function serialize(root: TreeNode | null): string {
  const out: string[] = [];
  (function dfs(n: TreeNode | null) {
    if (!n) { out.push('#'); return; }
    out.push(String(n.val));
    dfs(n.left);
    dfs(n.right);
  })(root);
  return out.join(',');
}
function deserialize(data: string): TreeNode | null {
  const vals = data.split(','); let i = 0;
  function build(): TreeNode | null {
    const v = vals[i++];
    if (v === '#') return null;
    const node = new TreeNode(+v);
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

// Serialize — BFS: drain a queue, emit '#' for null, enqueue BOTH children (nulls too)
function serializeBFS(root: TreeNode | null): string {
  if (!root) return '';
  const q: (TreeNode | null)[] = [root];
  const out: string[] = [];
  let front = 0;
  while (front < q.length) {
    const node = q[front++];          // plain queue drain — no per-level bookkeeping needed
    if (!node) { out.push('#'); continue; }
    out.push(String(node.val));
    q.push(node.left);                // enqueue both children, null or not,
    q.push(node.right);               // so their tokens map 1:1 to the queue order
  }
  return out.join(',');
}

// Deserialize — BFS: each dequeued node claims the next two tokens as its children
function deserializeBFS(data: string): TreeNode | null {
  if (!data) return null;
  const vals = data.split(',');
  const root = new TreeNode(parseInt(vals[0]));
  const q: TreeNode[] = [root];
  let front = 0, i = 1;
  while (front < q.length && i < vals.length) {
    const curr = q[front++];          // parent waiting to be wired to its two children
    if (vals[i] !== '#') {            // left child
      const left = new TreeNode(parseInt(vals[i]));
      curr.left = left;
      q.push(left);
    }
    i++;
    if (vals[i] !== '#') {            // right child
      const right = new TreeNode(parseInt(vals[i]));
      curr.right = right;
      q.push(right);
    }
    i++;
  }
  return root;
}

function generateTrees(n: number): (TreeNode | null)[] {
  function build(lo: number, hi: number): (TreeNode | null)[] {
    if (lo > hi) return [null];                 // ONE empty tree — NOT []
    const res: (TreeNode | null)[] = [];
    for (let r = lo; r <= hi; r++)
      for (const L of build(lo, r - 1))
        for (const R of build(r + 1, hi))
          res.push(new TreeNode(r, L, R));
    return res;
  }
  return build(1, n);
}

4.6 · Easy-tier must-knows — write these cold

FAANG "easy" tree questions are pure recall — none needs a new idea, each is the §1 contract with a one-line combine. If the sheet is the last thing you see, these are the ones an interviewer is most likely to fire. Have every one in your fingers.

// Max Depth (104) — the height IS the answer
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  const L = maxDepth(root.left);
  const R = maxDepth(root.right);
  return 1 + Math.max(L, R);
}

// Invert (226) — swap each node's two children, then recurse
function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  [root.left, root.right] = [root.right, root.left];   // 1) swap the children
  invertTree(root.left);                               // 2) invert each subtree
  invertTree(root.right);
  return root;
}

// Same Tree (100) — same shape AND same values
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;          // both empty → identical
  if (!p || !q) return false;         // exactly one empty → different
  if (p.val !== q.val) return false;  // values differ here
  const L = isSameTree(p.left, q.left);
  const R = isSameTree(p.right, q.right);
  return L && R;
}

// Symmetric (101) — is the tree its own mirror?
function isSymmetric(root: TreeNode | null): boolean {
  function mirror(a: TreeNode | null, b: TreeNode | null): boolean {
    if (!a && !b) return true;          // both empty → mirrored
    if (!a || !b) return false;         // one empty → not mirrored
    if (a.val !== b.val) return false;  // values differ
    const L = mirror(a.left, b.right);    // outer ↔ outer
    const R = mirror(a.right, b.left);    // inner ↔ inner
    return L && R;
  }
  if (!root) return true;
  return mirror(root.left, root.right);
}

// Path Sum (112) — does ANY root-to-leaf path total `target`?
function hasPathSum(root: TreeNode | null, target: number): boolean {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === target;   // a leaf
  const rest = target - root.val;
  const L = hasPathSum(root.left, rest);
  const R = hasPathSum(root.right, rest);
  return L || R;
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• traverse recursive pre/in/post · iterative pre/in/post · BFS levelOrder
• easy maxDepth · invertTree · isSameTree · isSymmetric · hasPathSum
• return-value diameter + maxPathSum (say the contract first)
• BST searchBST · insertIntoBST (rec + iter) · lcaBST · isValidBST (range + inorder) · kthSmallest · BSTIterator · deleteNode
• LCA lowestCommonAncestor
• construct buildTree + serialize/deserialize

For each DFS: write the three contract lines — RETURN, BASE, RECORD — as comments before the code.