Coding Interview PatternsMaximum Depth of Binary Tree
EasyTree Depth-First Search
Maximum Depth of Binary Tree
Explanation & Solution
Description
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Examples
Example 1:
```tree
[3, 9, 20, null, null, 15, 7]
`
Input:root = [3, 9, 20, null, null, 15, 7]
0
3
1
9
2
20
3
null
4
null
5
15
6
7
Output: 3
Explanation: The longest path is 3 → 20 → 15 (or 3 → 20 → 7), which has 3 nodes.
Example 2:
```tree
[1, null, 2]
`
Input:root = [1, null, 2]
0
1
1
null
2
2
Output: 2
Constraints
- The number of nodes in the tree is in the range
[0, 10⁴] -100 <= Node.val <= 100
Approach
Tree Depth-First Search pattern
1. Base Case
- If
rootisnull: - Return
0 - Reason:
- An empty tree has depth
0
2. Recurse on Left Subtree
- Call
solve(root.left) - This returns the maximum depth of the left subtree
3. Recurse on Right Subtree
- Call
solve(root.right) - This returns the maximum depth of the right subtree
4. Combine Results
- Calculate:
Math.max(left, right) + 1- Why:
- The depth at the current node is the deeper subtree plus
1for the current node itself
5. Return the Result
- The recursion bubbles up from leaves to root
- Each node returns the depth of its deepest descendant path
- The root returns the overall maximum depth
Key Insight
- This is a classic post-order traversal — process children before the parent
- At each node, we simply take the max of left and right depths and add 1
Time
O(n)visit each node onceSpace
O(h)recursion stack where h is tree heightVisualization
Input:
DFS Traversal[3, 9, 20, 15, 7]
output0
Press play to start DFS traversal
CurrentIn stackComplete
11 steps