Fresher · Trees

Maximum Depth of a Binary Tree

A node is {value, left, right}; missing children are null. Return the number of nodes on the longest root-to-leaf path. An empty tree has depth 0. The input is a finite tree with no cycles.

Examples

{value:1,left:{value:2,left:null,right:null},right:null} → 2

Compare approaches

Recursive depth first

Depth is one plus the larger child depth. A very deep tree can exceed the JavaScript call stack.

Time: O(n) · Space: O(h) call stack

function treeDepth(root) { if (!root) return 0; return 1 + Math.max(treeDepth(root.left), treeDepth(root.right)); }

Explicit stack

Use heap-allocated stack entries instead of recursive calls. Both algorithms are asymptotically optimal; the iterative version avoids call-stack overflow.

Time: O(n) · Space: O(h) auxiliary stack

function treeDepth(root) {
  if (!root) return 0;
  const stack = [[root, 1]];
  let best = 0;
  while (stack.length) {
    const [node, depth] = stack.pop();
    best = Math.max(best, depth);
    if (node.left) stack.push([node.left, depth + 1]);
    if (node.right) stack.push([node.right, depth + 1]);
  }
  return best;
}

Common traps

Distinguish height in edges from depth in nodes.
Neither algorithm accepts cyclic graphs.

Practise in the workspace →