Maximum Depth of Binary Tree — Problem Statement & Solution Guide
Problem Description
Given the root of a binary tree, find its maximum depth. The maximum depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node. The input is the root of the binary tree, and the output is the maximum depth of the binary tree.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Depth of Binary Tree"
WHY DOES IT MATTER?
Computing tree depth is a fundamental building block for many higher‑level algorithms, such as balancing operations, serialization, and evaluating hierarchical data structures. Mastery of this pattern demonstrates a candidate's ability to reason about recursion, stack usage, and level‑order processing.
OPTIMIZATION CHALLENGE
The key insight is to avoid recomputing depths for overlapping subtrees; by visiting each node exactly once and aggregating child results, we achieve linear time. Choosing between DFS (recursion) and BFS (queue) lets you trade off space based on tree shape.
REAL-WORLD CONNECTION
Think of a corporate org chart where the CEO is the root and each manager reports to a higher level. Determining the maximum depth is akin to finding the longest chain of command, which is crucial for understanding communication latency in distributed management systems.
During an interview, write the recursive solution first—it's concise and shows clear thinking. Then, if prompted, discuss the iterative BFS version and explicitly mention the call‑stack vs. queue space trade‑off, which signals depth of understanding.
COMPLEXITY AT A GLANCE
O(n)O(h)Core Theory — Why This Approach?
The maximum depth of a binary tree is a classic example of a tree traversal problem that can be solved efficiently using depth‑first search (DFS) or breadth‑first search (BFS). In a DFS approach, we recursively explore each subtree, computing the depth of the left and right children and returning the larger of the two plus one for the current node. This leverages the divide‑and‑conquer paradigm: the problem on a tree of size n is reduced to two sub‑problems on trees of size roughly n/2, yielding a linear time solution. A BFS solution uses a queue to process nodes level by level, counting how many levels are traversed until the queue empties, which also runs in O(n) time.
Naïve approaches, such as repeatedly scanning the tree to find leaf nodes or recomputing depths for overlapping subtrees, incur exponential time because they revisit the same nodes many times. For large trees (e.g., millions of nodes), such redundancy leads to timeouts and stack overflows. The optimal paradigm—either recursive DFS with memoization (implicit via the call stack) or iterative BFS—ensures each node is visited exactly once, guaranteeing O(n) time and O(h) auxiliary space, where h is the tree height (O(log n) for balanced trees, O(n) for degenerate ones).
Interview Questions on This Problem
Q1How would you compute the maximum depth of a binary tree iteratively without using recursion?
Use a queue for BFS: initialize the queue with the root, then while the queue is not empty, process all nodes at the current level, increment a depth counter, and enqueue their non‑null children. The depth counter after the loop ends is the maximum depth.
Q2What is the space complexity of a recursive DFS solution for maximum depth, and how does tree balance affect it?
The recursive DFS uses O(h) space for the call stack, where h is the height of the tree. In a perfectly balanced tree, h = O(log n), giving logarithmic space; in a skewed tree, h = O(n), leading to linear space.
Q3Can you modify the maximum depth algorithm to also return the deepest leaf node value? Explain your approach.
Perform a DFS that returns a pair (depth, leafValue). For each node, compute left and right results, pick the larger depth, and propagate the associated leaf value upward. In case of equal depths, choose either according to problem constraints.
Examples
Input
{3,9,20,null,null,15,7}Output
3
Explanation: Step-by-step: with input {3,9,20,null,null,15,7}, we calculate the depth of the left subtree (2) and the right subtree (3), and return the maximum depth which is 3.
Input
{1}Output
1
Explanation: Step-by-step: with input {1}, we calculate the depth of the tree which only contains one node, and return the depth which is 1.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Use a single DFS or BFS traversal that visits each node once, aggregating child depths (DFS) or counting levels (BFS) to compute the maximum depth in linear time.
Brute Force Approach
A naive method would repeatedly search for leaf nodes from the root, recomputing depths for the same subtrees many times, leading to exponential time.
Verified Code Solutions
function maxDepth(root) {
if (!root) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
}class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}class Solution:
def maxDepth(self, root):
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1function maxDepth(root) {
if (!root) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.