Maximum Depth of Binary Tree

The problem. 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. An empty tree has depth 0.

The tree 3, 9, 20, null, null, 15, 7. The longest root-to-leaf paths are 3 → 20 → 15 and 3 → 20 → 7, each with 3 nodes, so the maximum depth is 3. The path 3 → 9 has only 2.

Example

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

LeetCode's "depth" counts nodes, so it equals the height in edges plus one. The question is really: how many levels does the tree have?

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 6 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: list every root-to-leaf path
2. Optimal: count the levels with breadth-first search
3. Best solution: ask both children, add one
Comparing the three approaches
Edge cases to test
Variations

Prev Next

Mark completed

Was this helpful?

QueueFirst-in, first-out — the structure behind task scheduling and breadth-first traversal.4 lessons · 5 problems
StackLast-in, first-out — the structure behind call stacks, undo history, and expression parsing.6 lessons · 13 problems
Hash MapKey → value lookups in O(1) on average — the tool behind counting, “seen it before?” checks, prefix sums and sliding windows.4 lessons · 11 problems

Maximum Depth of Binary Tree

Example

Keep reading. It's free.

Keep exploring