Height is 1 + max of children

Why it matters

File browsers, render trees, and organizational hierarchies often need a depth limit before expanding, laying out, or validating nested data. Carrying complete root-to-leaf paths makes deep or skewed trees consume far more memory than the answer requires. The maximum depth must be found in one visit per node without copying any path.

Return the maximum depth of the binary tree. An empty tree has depth 0.

Input

root = [3, 9, 20, None, None, 15, 7]

Output

3

For [3, 9, 20, None, None, 15, 7], the brute walk copies paths such as [3, 20, 15]. Return 1 from leaves 9, 15, and 7 instead; then 20 returns 2 and 3 returns 3, with no path copies.

For [3, 9, 20, None, None, 15, 7], a None child returns 0. Node 9 receives 0 from both children and returns 1. Nodes 15 and 7 do the same, so each also returns 1.

Node 20 receives 1 and 1, then returns 1 + max(1, 1) = 2. Root 3 receives 1 from node 9 and 2 from node 20, so it returns 3. Each node reports one number; no call needs the path above it.