Maximum Depth of Binary Tree
Problem
Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
- The number of nodes in the tree is in the range [0, 10⁴]
- −100 ≤ Node.val ≤ 100
Example
root = [3,9,20,null,null,15,7]3Starting at the root node with value 3, the algorithm recursively explores the left subtree rooted at 9 and the right subtree rooted at 20. The left subtree has depth 1 (node 9 is a leaf), while the right subtree has depth 2 (nodes 20 -> 15 or 20 -> 7). The maximum depth is therefore 1 + max(1, 2) = 3. The critical moment is the recursive calls returning depths for left and right subtrees, allowing the algorithm to combine these results to compute the overall maximum depth.
Approach
Straightforward Solution
A brute-force approach might attempt to traverse all paths and track the maximum length explicitly, but this would be more complex and less elegant. The straightforward recursive DFS directly encodes the definition of maximum depth.
Core Observation
The maximum depth of a binary tree is defined recursively: it is 1 plus the maximum depth of its left and right subtrees. This naturally suggests a depth-first traversal where each node's depth depends on its children's depths.
Path to Optimal
Recognizing that the problem's recursive structure matches the tree's definition leads to a simple DFS solution. The key insight is that the maximum depth at any node is 1 plus the maximum of the depths of its left and right children. This allows the problem to be solved cleanly with a post-order traversal, where the depths of children are computed before the parent.
Optimal Approach
Use a recursive DFS function that returns 0 if the node is null (base case). Otherwise, recursively compute the maximum depth of the left and right subtrees, then return 1 plus the greater of these two depths. This approach is both conceptually simple and efficient, running in O(n) time where n is the number of nodes.
Time
O(n)
Each node is visited exactly once in the recursive traversal, resulting in linear time proportional to the number of nodes.
Space
O(h)
The recursion stack depth is proportional to the height h of the tree. In the worst case (skewed tree), this can be O(n), but for balanced trees, it is O(log n). This is auxiliary space excluding the input tree.
Pattern Spotlight
DFS (Post-Order Traversal for Tree Depth)
When computing a property that depends on child nodes in a tree, use post-order DFS to first gather child results before combining them at the parent, enabling clean recursive definitions.
Solution
| 1 | class Solution:
|
| 2 | def maxDepth(self, root: TreeNode) -> int:
|
| 3 | if not root:
|
| 4 | return 0
|
| 5 |
|
| 6 | left_depth = self.maxDepth(root.left)
|
| 7 | right_depth = self.maxDepth(root.right)
|
| 8 |
|
| 9 | return 1 + max(left_depth, right_depth) |
| 1 | class Solution { |
| 2 | public int maxDepth(TreeNode root) { |
| 3 | if (root == null) { |
| 4 | return 0; |
| 5 | } |
| 6 | |
| 7 | int leftDepth = maxDepth(root.left); |
| 8 | int rightDepth = maxDepth(root.right); |
| 9 | |
| 10 | return 1 + Math.max(leftDepth, rightDepth); |
| 11 | } |
| 12 | } |
Step-by-Step Solution
Return 0 for Null Nodes to Define Base Case Depth
| 3 | if not root:
|
| 4 | return 0
|
Objective
To handle the base case of recursion by returning zero depth for null nodes.
Key Insight
The base case is essential to terminate recursion and correctly represent the depth of an empty subtree as zero. This allows the recursive calls to build up the depth count accurately from the leaves upward.
Interview Quick-Check
Core Logic
Returning 0 for null nodes defines the depth of an empty subtree, enabling the recursive formula to work correctly.
State & Boundaries
This base case prevents infinite recursion and marks the boundary condition for leaf nodes.
Recursively Compute Left and Right Subtree Depths
| 6 | left_depth = self.maxDepth(root.left)
|
| 7 | right_depth = self.maxDepth(root.right)
|
Objective
To explore the left and right subtrees and obtain their maximum depths.
Key Insight
By recursively calling the function on left and right children, the algorithm gathers the depth information needed to compute the current node's depth. This post-order traversal ensures child depths are known before combining them.
Interview Quick-Check
Core Logic
Recursive calls to left and right children compute their depths, which are the building blocks for the parent's depth.
Common Pitfalls & Bugs
Forgetting to recurse on both children or mixing up left and right can lead to incorrect depth calculations.
Return 1 Plus Maximum of Left and Right Depths to Aggregate Result
| 9 | return 1 + max(left_depth, right_depth) |
Objective
To combine the depths of left and right subtrees and add one for the current node.
Key Insight
The maximum depth at the current node is one more than the maximum depth of its children. This aggregation step embodies the recursive definition of tree depth and ensures the final result reflects the longest path from root to leaf.
Interview Quick-Check
Core Logic
Returning 1 + max(left_depth, right_depth) correctly computes the depth at the current node by adding the current level.
State & Boundaries
This return value propagates up the recursion stack, enabling the root to receive the maximum depth of the entire tree.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
return 1 + max(left_depth, right_depth)Return one plus the maximum of left and right subtree depths.
This line embodies the recursive definition of maximum depth, combining child depths and adding one for the current node, which is the core logic that solves the problem.
if not root:Check if the current node is null to handle the base case.
This base case is critical to terminate recursion and correctly represent the depth of an empty subtree as zero, which is foundational for the recursive depth calculation.
return 0Return 0 for null nodes indicating zero depth.
Returning zero here ensures that leaf nodes compute their depth as 1 (1 + max(0,0)) and that recursion unwinds correctly with accurate depth values.
left_depth = self.maxDepth(root.left)Recursively compute the maximum depth of the left subtree.
This recursive call explores the left child, gathering depth information needed to compute the current node's depth, following a post-order traversal pattern.
right_depth = self.maxDepth(root.right)Recursively compute the maximum depth of the right subtree.
This recursive call explores the right child, complementing the left subtree's depth to enable correct aggregation at the current node.
Test Your Understanding
Why does the recursive function return 0 for a null node, and how does this base case affect the overall depth calculation?
Returning 0 for a null node correctly represents that an empty subtree has depth zero, which serves as the base case for recursion. This ensures that leaf nodes return a depth of 1 (1 + max(0,0)) and that the depth calculation correctly aggregates upwards.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Maximum Depth of Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Depth of Binary Tree drill