Maximum depth of a binary tree

Easy TimeO(n) SpaceO(h)

The depth of a tree is how many nodes lie along the longest path from the root down to a leaf, so a single node has depth 1 and an empty tree has depth 0. Given the root of a binary tree, return its depth. Depth counts nodes rather than the edges between them, and it is the longest such path that is wanted, not the shortest.

Examples

Example 1

Input
node = buildTree()
Output
3
Three nodes along the longest root-to-leaf path, such as 4 → 2 → 1.

Example 2

Input
node = null
Output
0
No nodes at all, so the depth is 0 rather than 1.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function maxDepth(node) {
  if (node === null) return 0;
  const left = maxDepth(node.left);
  const right = maxDepth(node.right);
  return Math.max(left, right) + 1;
}
maxDepth(buildTree());
Done

The first 8 calls, of 16. This one does not fit on a page.

Step through maxDepth(buildTree()) call by call

More like this

All binary trees examples (9) →