Maximum Depth of Binary Tree
Easy1 + max(left depth, right depth)
Dive as deep as you can down each branch; the deepest you go is the tree's height.
The idea
A tree's depth is one plus the deeper of its two subtrees. Recurse to the leaves (depth 0) and let the answers bubble back up.
The trick
- A tree's height is the longest root-to-leaf path; depth counts those same edges from the top.
- Post-order recursion lets each node answer using its children's already-computed depths.
Step 1 of 8. A node's height is 1 + the taller of its two subtrees. Solve leaves first, then bubble up.
1/8
Optimal
timeO(n)spaceO(h)
Post-order combine.
1function depth(node) {2 if (!node) return 0;3 return 1 + Math.max(depth(node.left), depth(node.right));4}Input
- nodes
- 6, 5 edges
Output
- max depth
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,9,20,null,null,15,7]
- Output:
- 3
- Explanation:
- The longest root-to-leaf path has 3 levels.
Example 2
- Input:
- tree = [1,null,2]
- Output:
- 2
- Explanation:
- Root plus one child → depth 2.
Example 3
- Input:
- tree = []
- Output:
- 0
- Explanation:
- An empty tree has depth 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.