Maximum Depth of Binary Tree
The Prompt
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.
Understanding the Problem
The maximum depth is the number of nodes on the longest root-to-leaf path. A single node has depth 1; an empty tree has depth 0.
The recursive reframe: a tree's depth is 1 (for the root) plus the depth of its deeper subtree. Each node only needs two numbers from below — the depths of its left and right subtrees — to know its own answer.
The Interview Flow
Interviewer
How do you find the maximum depth of a binary tree?
Candidate
This is a classic recursive problem. The depth of a tree is related to the depths of its subtrees.
Interviewer
Can you elaborate on that relationship?
Candidate
The depth of any node is `1 + max(depth of left subtree, depth of right subtree)`. The base case is a null node, which has a depth of 0.
Interviewer
So, for the root node, you would recursively find the max depth of its left and right children and then add one?
Candidate
Exactly. The function would call itself on the left child and the right child. It would take the maximum of the two returned values and add 1 to it before returning.
Interviewer
That sounds perfect. How could this be solved iteratively?
Candidate
Iteratively, I could use a Breadth-First Search (BFS) with a queue. I would process the tree level by level. I'd keep a count of the levels. The total number of levels I process is the maximum depth. In each iteration of the main loop, I process all nodes on the current level by getting the queue's size, and then I add all their children to the queue for the next level.
Interviewer
Both methods work. The recursive one is very intuitive for this problem. Please implement it.
Why does recursion carry the whole proof?
The invariant is that maxDepth(node) returns the true depth of the subtree rooted at node. It holds for the base case (null → 0), and if it holds for both children, then 1 + max(left, right) is exactly the longest downward path through this node. Induction on subtree height makes the root call correct.
Every node is visited once and does O(1) work combining child results, so time is O(n). Space is O(h) for the call stack — O(log n) for a balanced tree, O(n) if the tree degenerates into a chain.
Recursive DFS Solution
- Define a function `maxDepth` that takes a `root` node.
- Handle the base case: if `root` is `null`, the depth is 0, so return 0.
- Recursively call `maxDepth` on the left child to get the depth of the left subtree: `leftDepth = maxDepth(root.left)`.
- Recursively call `maxDepth` on the right child to get the depth of the right subtree: `rightDepth = maxDepth(root.right)`.
- The depth of the tree rooted at the current node is the maximum of the depths of its subtrees, plus one for the current node itself.
- Return `1 + Math.max(leftDepth, rightDepth)`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function maxDepth(root) {
if (root === null) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}Explanation
Compute the depth of the tree [3, 9, 20, null, null, 15, 7] — answers bubble up from the leaves.
1Leaves report first: 9, 15, and 7 each have null children (depth 0), so each returns 1 + max(0, 0) = 1.
2Node 20 combines its children: 1 + max(1, 1) = 2. Its subtree is 2 nodes tall on the longest path.
3The root takes the deeper side: 1 + max(1, 2) = 3. Maximum depth is 3, along the path 3 → 20 → 15 (or 3 → 20 → 7).
Complexity Analysis
TIME
O(n)
SPACE
O(h)
Finished working through this one?
Mark it complete to track it on your Data Structures path.