Trees: what does each call return?

Solve a tree one node at a time. First decide what a call should return for the subtree under a node. Then trust the recursive calls on the children to return exactly that, and combine their answers. When the question is about levels or the nearest something, go level by level with a queue instead.

Think of it like this: a company org chart. To count everyone, the CEO asks each direct report “how many people are in your team, including you?” Each manager asks their own reports the same question, and the answers flow back up. That's depth-first. Reading the chart row by row is breadth-first: the CEO first, then every VP, then every manager.

How to spot it

Words and constraints in a problem that point to this pattern:

• The input is a TreeNode called root
• “Depth”, “height”, “balanced”, “diameter”: an answer built from the children's answers
• “Level by level”, “each row”, “rightmost node of each level”, “nearest leaf”: breadth-first
• “Valid binary search tree” or “values in sorted order”: in-order traversal
• “Path from the root to a leaf”: carry information down as a parameter

Watch it work

The template

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Depth-first. First write the contract: "dfs(node) returns ___ for the subtree under node".
function dfs(node: TreeNode | null): number {
  if (node === null) return 0;        // base case: the answer for an empty subtree
  const fromLeft = dfs(node.left);    // trust it: the answer for the left subtree
  const fromRight = dfs(node.right);  // and for the right subtree
  return fromLeft + fromRight + node.val; // combine them with this node (here: a sum)
}

// The three orders: only the position of "look at node" changes.
function orders(node: TreeNode | null, pre: number[], inOrder: number[], post: number[]): void {
  if (node === null) return;
  pre.push(node.val);                 // pre-order: node first
  orders(node.left, pre, inOrder, post);
  inOrder.push(node.val);             // in-order: between the children (sorted in a BST)
  orders(node.right, pre, inOrder, post);
  post.push(node.val);                // post-order: after both children
}

// Breadth-first, one level per round: here, the largest value on each level.
function largestPerLevel(root: TreeNode | null): number[] {
  const result: number[] = [];
  if (root === null) return result;
  let level: TreeNode[] = [root];     // every node on the current level
  while (level.length > 0) {
    const next: TreeNode[] = [];      // the level below, filled as we go
    let best = -Infinity;
    for (const node of level) {
      best = Math.max(best, node.val);         // the per-level work goes here
      if (node.left !== null) next.push(node.left);
      if (node.right !== null) next.push(node.right);
    }
    result.push(best);
    level = next;                     // move down one level
  }
  return result;
}

Worked example

1. The first idea: collect every root-to-leaf path into an array of arrays, then add up each one. It works, but it builds and stores every path, which is a lot of copying for a big tree.

2. Notice that you never need the whole path, only how much is still missing. So carry a number down instead: remaining, which shrinks by each node's value on the way down. Information that flows down goes in a parameter. Information that flows up is the return value.

3. Write the contract: hasPathSum(node, remaining) returns true if some path from node down to a leaf adds up to remaining. Base cases: an empty subtree has no path, so false. A leaf succeeds exactly when its value equals remaining.

4. Combine: ask each child with what's left after this node, and succeed if either child does.

   function hasPathSum(node: TreeNode | null, remaining: number): boolean {
     if (node === null) return false;                       // no node, no path
     if (node.left === null && node.right === null) {
       return node.val === remaining;                       // a leaf: does it finish the sum?
     }
     const rest = remaining - node.val;                     // what the children still need
     return hasPathSum(node.left, rest) || hasPathSum(node.right, rest);
   }
   

5. Run it with 12: node 5 leaves 7 → node 3 leaves 4 → leaf 1: 1 === 4? no → leaf 4: 4 === 4, true. The || stops there, so node 8 is never visited.

6. Edge cases: an empty tree returns false, even for target 0. A root 5 with only a left child 3 and target 5 returns false, because 5 isn't a leaf. That's why the leaf check is separate from the null check: a node with one child must not count as the end of a path.

Common mistakes

• Forgetting the base case if (node === null): the recursion reaches a missing child and crashes with “Cannot read properties of null (reading 'left')”.
• Treating a node with one child as a leaf: a leaf has no children. Checking only node.left === null accepts half-finished paths.
• Calling dfs(node.left) and dfs(node.right) but never returning the combined value: every call returns undefined, and the answer is NaN or wrong.
• Using queue.shift() on a big tree: each shift moves every element, so the search becomes O(n²). Use a level array plus a next array, or an index pointer.
• Pushing children into the same array you're looping over in BFS: the levels blur together, and per-level answers mix rows. Use a separate next array or save queue.length before the loop.

Cost

In interviews