Maximum Depth of Binary Tree

EasyTreesTreeDFSBFSBinary Tree

Problem

You are given the root of a binary tree and need its maximum depth: the number of nodes along the longest path from the root down to any leaf. An empty tree has depth 0.

Example. A root 3 with a left child 9 (a leaf) and a right child 20 that has children 15 and 7 has maximum depth 3, from 3 to 20 to 15 (or 7).

Key idea

Enumerating every root-to-leaf path and taking the longest duplicates work, since many paths share the same prefix near the root. A tree's depth depends only on the depths of its two subtrees: it is one more than whichever subtree is deeper.

That observation is the whole recursion. For a null node, the depth is 0. Otherwise, compute the left and right subtree depths independently, take the larger, and add one for the current node. Each node contributes one comparison and one addition, so the whole tree is processed in a single pass. The same idea works with a breadth-first sweep: process the tree level by level with a queue, and count how many levels complete before it empties, a natural fit since depth is really a level count.

Solution

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 === null) {
    // empty subtree contributes no depth
    return 0;
  }

  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);

  // depth is one more than the deeper of the two subtrees
  return 1 + Math.max(leftDepth, rightDepth);
}

Complexity

  • Time: O(n). Every node is visited exactly once, whether by depth-first or breadth-first traversal.
  • Space: O(h). The recursive call stack holds one frame per level; a breadth-first version instead uses O(w) for the widest level, up to O(n).

Watch out for

  • A single node has depth 1, not 0: the base case is the empty, null tree, not the leaf.
  • Do not confuse depth, root to a node, with height measured downward from it; for the maximum they coincide, but the direction differs.
  • A chain-shaped tree makes recursion depth proportional to n, worth remembering if stack limits matter.

Pattern

This is the base case of post-order aggregation: compute a value for each child subtree, then combine the results at the parent. Nearly every tree metric, including depth, diameter, balance, and sum, follows this shape of asking children first and combining last.

Related questions