March 24
Maximum Depth of Binary Tree
How to measure tree height by thinking about leaves, subtrees, and the combination 1 + max(left, right).
Trees Beginner 10 min TypeScript
Given the root of a binary tree, return its maximum depth.
Maximum depth is the number of nodes along the longest path from the root down to a leaf.
Example:
Input: [3,9,20,null,null,15,7]
Output: 3
What to notice before coding
- An empty tree returns `0`.
- A leaf returns `1`, not `0`.
- The problem asks for the longest path, so you want `max`, not `min`.
Common mistakes
- returning `0` for a leaf and shifting the whole answer
- using the smaller side instead of the larger one
Step 1 - Translate the prompt into a smaller question
"Maximum depth" can feel abstract at first.
But the real question is:
- how many nodes exist along the longest path to a leaf?
Step 2 - Write a baseline that makes that visible
A good baseline is traversing the tree by levels with BFS:
- start with the root
- process one full level
- increment the depth
When the queue is empty, you know how many levels existed.
Step 3 - Notice the recursive rule
For any node:
- the left depth is one subproblem
- the right depth is another subproblem
- the current answer is
1 + max(...)
That is the center of the problem.
Step 4 - Define the base case correctly
The base cases are:
null-> depth0- leaf ->
1, because the current node counts
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function maxDepth(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(h)
Solution 1 - Level-order BFS
Good baseline because it makes the idea of “how many floors exist” very concrete.
export function maxDepth(root) {
if (root === null) {
return 0
}
const queue = [root]
let depth = 0
while (queue.length > 0) {
const levelSize = queue.length
depth += 1
for (let index = 0; index < levelSize; index += 1) {
const node = queue.shift()
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
}
return depth
}It works well. But recursion captures the definition of the problem more directly.
Solution 2 - Recursive DFS with recursion
Now the solution follows the definition of depth itself.
export function maxDepth(root) {
if (root === null) {
return 0
}
const leftDepth = maxDepth(root.left)
const rightDepth = maxDepth(root.right)
return 1 + Math.max(leftDepth, rightDepth)
}Short, direct, and aligned with the prompt.
What to say in the interview
A strong short explanation would be:
I can count levels with
BFS, but the most direct version is recursive. The depth of a node is 1 plus the larger depth between left and right. The base case isnull -> 0.
That shows that you:
- connected the prompt to a simple recursive definition
- separated base case and combination clearly
- can explain tree recursion without getting lost in visualization
When this pattern shows up again
The same pattern comes back when you need to:
- calculate height or size in a tree
- solve for the children and combine at the parent
- think in recursive
DFS - open the door to balanced tree, diameter, and many other questions
The point is not memorizing
maxDepth.
The point is seeing that many tree questions become “solve the children and combine”.