LeetCode 104 · Easy · Trees

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to a leaf.

O(n)time
O(h)space · call stack
DFSrecursion · 1 + max

level order as on LeetCode, null = no child · up to 15 nodes, 4 levels · values −99 to 99

Call stack one frame per maxDepth call · newest on the right · badges = returned depth

public int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return 1 + Math.max(left, right);}
root
—
left
—
right
—
return
—
frames
0

Why it works

  1. The definition is the code. An empty tree has depth 0; any other tree is its root plus the deeper of its two subtrees, so 1 + max(left, right).
  2. Brute force walks every root-to-leaf path separately, re-counting shared upper nodes: up to O(n·h). The recursion answers each subtree once and reuses it: O(n).
  3. Answers flow upward (post-order). A node can only return after both children have, so badges fill in from the leaves to the root. The stack holds one frame per level: O(h) space.
  4. Pitfall: the base case must return 0 for null, not 1 for a leaf only. A node with one child still has a null child, and max safely ignores its 0. (Minimum Depth is the trap: there min would pick that 0.)
  5. Iterative BFS: run the level-order loop from problem 102 and count the levels. Iterative DFS: a stack of node and depth pairs, keeping the largest depth seen. Both O(n), and no StackOverflowError on a very deep tree.