Practice Maximum Depth of Binary Tree
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Maximum Depth of Binary Tree
Problem Statement
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.
Source: Maximum Depth of Binary Tree on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
root = [3,9,20,null,null,15,7]
3
# Example 2
root = [1,null,2]
2
Constraints
How to solve Maximum Depth of Binary Tree
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
The depth of a tree is one more than the larger of its two subtree depths, and an empty subtree has depth zero. That single recurrence visits every node once.
Why brute force is not enough
Collect every root-to-leaf path as an explicit list and return the longest length. Copying paths costs O(n * h) time and memory; for a skewed tree at the 10^4-node limit that is on the order of 10^8 node references for an answer that needs one integer.
Approach
- Define the depth of an empty subtree as 0.
- For a present node, its depth is 1 plus the maximum of the depths of its left and right subtrees. Invariant: the value returned for a node is the number of nodes on the longest downward path that begins at that node.
- Return the depth computed at the root.
- An iterative breadth-first version counts rounds of a level-order traversal; the number of rounds is the depth, and it avoids deep recursion on a long chain.
- An iterative depth-first version pushes node and depth pairs onto a stack and tracks the largest depth seen.
Walkthrough of Example 1
root = [3,9,20,null,null,15,7] → 3
- Node 9 has no children, so its depth is 1 + max(0, 0) = 1.
- Nodes 15 and 7 are leaves with depth 1 each, so node 20 has depth 1 + max(1, 1) = 2.
- The root 3 has depth 1 + max(1, 2) = 3.
- Return 3; the longest paths are 3, 20, 15 and 3, 20, 7.
Time and space
Time O(n) · Space O(h). n is the node count and h the height; each node is visited once, and the recursion stack holds one root-to-node path, which is O(n) for a chain.
Interview pitfalls
- Returning 1 instead of 0 for an empty subtree, which inflates every depth by one; the tree 1 with a single right child 2 would report 3 instead of 2.
- Counting edges instead of nodes; this problem defines a single node as depth 1.
- Forgetting that an empty tree returns 0.
- Ignoring recursion limits; a 10^4-node chain exceeds the default stack depth in some languages, so be ready with the iterative version.
- Carrying over logic from minimum depth, where a node with exactly one child must not treat the missing side as a leaf.
Follow-up questions interviewers ask
- Find the minimum depth, the shortest path from the root to any leaf, and explain why the missing-child case differs.
- Compute the diameter of the tree, the longest path between any two nodes, with the same post-order recursion.
- Decide whether the tree is height-balanced in a single pass without recomputing heights.
Further reading on the technique: Depth-first search
Related LeetCode Problems
Practice more problems similar to Maximum Depth of Binary Tree.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.