Part 2 · Problems · Trees and BFS
Maximum Depth of Binary Tree
#104 · Easy · LeetCode
Return the number of nodes on the longest root-to-leaf path.
[3,9,20,null,null,15,7] -> 3
Ask before coding
- Empty tree is 0?
Hint
Depth of a node = 1 + depth of its deeper child.
Approach
Recursion: null is 0, otherwise 1 + max of left and right.
Time O(n) Space O(h), h = height
Watch it run
Solution (JavaScript, tested)
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}Traps
- Very deep trees can overflow the call stack. BFS level count avoids that.
Say out loud: Recursive definition, each node visited once. Stack depth is the tree height.