104. Maximum Depth of Binary Tree

Approach

What is This Problem?

Given the root of a binary tree, return its maximum depth - the number of nodes along the longest path from the root down to the farthest leaf node.

Why This Works

The depth of a tree is defined recursively:

• An empty tree has depth 0.
• A non-empty tree’s depth is 1 (for the root) plus the maximum depth of its left and right subtrees.

This works because:

• Each level adds 1 to the depth count.
• The longest path will be determined by the subtree with greater depth.
• Recursion naturally explores all root-to-leaf paths and returns the maximum.

Algorithm Steps

1. Base case: if root is null, return 0.
2. Recursively compute depth of left subtree.
3. Recursively compute depth of right subtree.
4. Return 1 + max(leftDepth, rightDepth).

Visualization

Example tree:

      3
     / \
    9  20
       / \
      15  7

Depth calculation:

maxDepth(3):
  left = maxDepth(9) → leaf → returns 1
  right = maxDepth(20):
    left = maxDepth(15) → leaf → 1
    right = maxDepth(7) → leaf → 1
    right = 1 + max(1,1) = 2
  return 1 + max(1,2) = 3

Longest path: 3 → 20 → 15 (or 3 → 20 → 7), depth = 3 nodes.

Key Pattern

• Recursive tree traversal: Process node, then children
• Post-order style: Compute child depths before current node’s result
• Base case: null node returns 0
• Combine results: 1 + max(left, right)

When to Use This Pattern

• Computing height/depth of any tree (binary, n-ary)
• When you need to know the longest root-to-leaf path
• Often used in balanced tree checks (AVL, etc.)
• Adaptable to compute other aggregations (min depth, max sum path, etc.)

Solution

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

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

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;

  let leftSubTree = maxDepth(root.left);
  let rightSubTree = maxDepth(root.right);

  return 1 + Math.max(leftSubTree, rightSubTree);
}

const treeNode3 = new TreeNode(3);
const treeNode9 = new TreeNode(9);
const treeNode20 = new TreeNode(20);
const treeNode15 = new TreeNode(15);
const treeNode7 = new TreeNode(7);

treeNode3.left = treeNode9;
treeNode3.right = treeNode20;
treeNode20.left = treeNode15;
treeNode20.right = treeNode7;

console.log(maxDepth(treeNode3));