Example 1
ready- Input
root = [ 3, 9, 20, null, null, 15, 7 ]- Expected
3- Why
- the longest root-to-leaf route contains 3 nodes
Maximum Depth of Binary Tree
25 min · maxDepth()A family tree can look shallow on one side and keep stretching for generations on the other. A binary tree is a tree where each node has at most two children, and your job is to measure how far its longest branch reaches.
Given the tree's root, return its maximum depth. Depth is the number of nodes on a
path from the root down to a leaf, including both ends.
A few ground rules:
- A leaf is a node with no children.
- A tree containing only its root has depth
1. - An empty tree has depth
0. - Node values don't affect the answer; only the tree's shape does.
Constraints
0 <= number of nodes <= 10_000-1_000 <= node.val <= 1_000
Hints
Count complete levels
If you scan the tree one level at a time, each finished level adds exactly one to the answer. What data structure keeps the next level waiting in order?
Ask each subtree
A non-empty node can ask its left and right subtrees for their depths. Which answer matters, and what does the current node add?
Name the base case
An absent child contributes depth 0. That gives you
1 + max(left_depth, right_depth) for every real node.
Follow-up
Could you compute the same answer without recursion, even when the tree is a single branch thousands of nodes deep?
Visible cases
Examples
Example 2
ready- Input
root = []- Expected
0- Why
- an empty tree has no levels
Example 3
ready- Input
root = [ 1, null, 2 ]- Expected
2- Why
- the only branch contains the root and its right child
Interview signal
Asked at
AmazonGoogleMeta
Level-order traversal — count finished layers
Breadth-first search (BFS) visits every node at one depth before moving to the next. Keep the current frontier in a queue. Each time you consume one whole frontier, you've finished another level.
from collections import deque
def max_depth(root: TreeNode | None) -> int:
if root is None:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return depthTime O(n) — every node enters and leaves the queue once. Space O(w) — the queue
holds at most one level's width, w.
Recursive depth-first search — let subtrees report back
The depth of an empty subtree is 0. For any real node, take the deeper child result
and add one for the current node. That recurrence is the whole algorithm.
def max_depth(root: TreeNode | None) -> int:
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))The two recursive calls solve smaller trees, and max discards the shallower branch.
Every node contributes exactly once to one of those calls.
Time O(n) — every node is visited once. Space O(h) — the call stack follows at
most one root-to-leaf path of height h.
Python's default recursion limit is close to 1,000 calls, while a valid tree here can be a 1,200-node line. Use the iterative BFS version above for untrusted tree depth; its queue replaces the risky call stack.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite