Maximum Depth of Binary Tree

Examples

Input: root = [3,9,20,null,null,15,7]
Output: 3

The longest path is 3 -> 20 -> 15 (or 3 -> 20 -> 7), which visits 3 nodes.

Input: root = [1,null,2]
Output: 2

The path 1 -> 2 visits 2 nodes; there's no longer path.

Input: root = []
Output: 0

An empty tree has no nodes, so its depth is 0.

Constraints

• The number of nodes in the tree is in the range [0, 10^4].

• -100 <= Node.val <= 100

Approach

The depth of a node is 1 (for itself) plus the larger of its left and right subtree's depths. That's a recursive definition: an empty tree has depth 0, and everything else is built up from its children's depths.

You can compute this top-down with plain recursion, or bottom-up with an iterative level-order traversal (BFS) that simply counts how many levels it processes before the queue empties.

Solutions

Recursive DFS

The depth of an empty node is 0. Otherwise, it's 1 plus the deeper of the left and right subtree depths.

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

function maxDepth(root) {
  if (root === null) return 0;

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

  return 1 + Math.max(leftDepth, rightDepth);
}

Time: O(n) · Space: O(h) — recursion stack depth, where h is the tree's height (O(n) worst case)

Iterative BFS

Process the tree level by level using a queue. Each full pass through the current level is one unit of depth; count how many passes happen before the queue is empty.

function maxDepth(root) {
  if (root === null) return 0;

  let depth = 0;
  let queue = [root];

  while (queue.length > 0) {
    const nextLevel = [];

    for (const node of queue) {
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }

    queue = nextLevel;
    depth++;
  }

  return depth;
}

Time: O(n) · Space: O(n) — the queue can hold up to a whole level of nodes