Maximum Depth of Binary Tree

Return the number of nodes on the longest root-to-leaf path of a binary tree. (LC 104)

If trees are new to you, this is the front door. It's the smallest problem that teaches the whole idea: you don't traverse a tree, you trust the recursion to have already traversed it for you.

The recipe

Say before you type: "The depth of a tree is one — for the node I'm standing on — plus the depth of its deeper child. An empty tree is zero."

1. Base case: null has depth 0.
2. Recursive case: ask each child for its depth, take the max, add 1 for yourself.

That's genuinely the whole algorithm.

The code

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

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

Why this shape

A tree is a recursive data structure — every node is the root of its own subtree — so a recursive definition maps onto it with no translation: depth(tree) = 1 + max(depth(left), depth(right)). The code is the definition.

The insight worth internalizing: the call stack is your traversal state. You never write a loop, never track a queue, never remember where you've been — the language runtime does it. Every "harder" tree problem (same tree, invert, path sum, diameter) is this exact skeleton with a different combination step where Math.max sits.

Complexity

This is the problem where interviewers probe whether you understand recursion's cost, so narrate it precisely:

	Cost	Because
Time	O(n)	Every node is visited exactly once
Space	O(h)	The recursion stack holds one frame per level currently being explored

And the follow-up you should volunteer before they ask: h depends on the tree's shape. Balanced → h = log n. A degenerate chain (every node has one child) → h = n, and the "tree" is secretly a linked list. Saying "O(h), which is log n balanced and n skewed" is the difference between reciting and understanding.

Traps

• Forgetting the base case returns 0, not 1 — a null is an empty tree, a leaf is depth 1 (its own 1 + on two zeros).
• Writing traversal machinery (stacks, visited sets) a tree doesn't need. There are no cycles in a tree; the recursion can't revisit anything.
• Being unable to explain the space complexity. The code is three lines; the complexity narration is the actual interview content.

The pattern this trains

Tree recursion: solve for the children, combine, add yourself. Level Order Traversal (LC 102) is the deliberate contrast — the one common tree question where recursion is not the natural fit, because "level by level" is breadth, not depth.