Maximum Depth of Binary Tree
Return the maximum depth of a binary tree — the number of nodes on the longest path from the root down to a leaf.
- The number of nodes in the tree is in the range [0, 10⁴].
- -100 <= Node.val <= 100
Intuition
The maximum depth of binary tree is the number of nodes on the longest path from the root down to a leaf. The recursive definition is so direct that the code is almost a transcription of the sentence.
A node's depth is one — for itself — plus the depth of its deeper subtree. An empty tree has depth zero. Those two facts are the complete solution:
- depth(node) = 1 + max(depth(left), depth(right)), with an empty node returning 0.
What is worth noticing is the shape of that recursion. Both children must return before the parent can combine them, which makes this a post-order traversal in disguise. Answers are computed at the leaves and bubble upward, with each node doing one comparison. No global counter, no depth parameter passed down — each call simply returns a number.
That bottom-up pattern is the same one behind Balanced Binary Tree, Diameter of Binary Tree, and Maximum Path Sum, all of which compute a height while recording something extra on the way up. Recognising it here makes those harder problems familiar rather than novel.
The iterative alternative is a level-order BFS that counts levels instead of recursing. It costs the same O(n) and is worth reaching for on a very deep, skewed tree where the recursion stack could overflow.
The purest bottom-up recursion: a node's depth is one more than the deeper of its two subtrees, and an empty tree is 0. This 1 + max(left, right) shape recurs across tree problems — diameter, balance checking, and height-based DP all compute it as a side effect.
Approach
Before reading on: price up what plain recursion costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Take the empty tree as depth zero
A null node contributes nothing, so return 0. This base case is what terminates every branch, and it also handles an entirely empty input without a separate check at the top.
Combine the two children
Return 1 + max(depth(left), depth(right)) — one for the current node plus the deeper of its two subtrees. Taking the maximum rather than the sum is the whole distinction from problems that measure total path length.
Recognise the post-order shape
Both recursive calls must complete before the parent can combine them, so work happens on the way up from the leaves. This bottom-up pattern recurs in Balanced Binary Tree and Diameter of Binary Tree, where the same height computation carries an extra result alongside it.
Trace how answers accumulate
Leaves compute 1 + max(0, 0) = 1. Their parents take the larger child answer and add one, and so on to the root. No state outside the recursion is needed — each call returns a number and the structure assembles them.
Use BFS when depth is a concern
A level-order traversal counts levels: process one full level, increment the counter, enqueue the next. Same O(n) cost, no recursion stack — the version to choose when the tree may be a long skewed chain.
Cost of the traversal
Every node is visited once and does O(1) work, giving O(n) time. Space is O(h) for the recursion stack, which is O(log n) on a balanced tree and O(n) in the degenerate case.
Solution & live demo
Common pitfalls
Returning 1 for a null node
if not root:
return 1if not root:
return 0The empty tree has no levels. Returning 1 inflates every path by one and reports a depth one too large for every input, including single-node trees.
Adding instead of taking the max
return 1 + left + right
return 1 + max(left, right)
That counts total nodes on both sides rather than the longest single root-to-leaf path. Depth is about one path, not the whole subtree.
Tracking depth with a mutable global and forgetting to restore it
self.d += 1 dfs(node.left) dfs(node.right)
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
A shared counter incremented on the way down must be decremented on the way back up, or sibling subtrees inherit each other's depth. Returning the value makes the bookkeeping impossible to get wrong.
Edge cases
not root → return 0 immediately.
One side is always empty (depth 0); the recursion effectively walks the chain, and depth equals node count.
Both subtrees report equal depth; max just picks either and adds one.