The problem
Return the maximum depth of a binary tree: the number of nodes on the longest path from the root down to a leaf.
Input: [3, 9, 20, null, null, 15, 7] Output: 3
Picture it
Picture a folder tree on a computer. To know how deep it goes, each folder asks its two subfolders “how deep are you?” and answers 1 + the deeper of the two. An empty spot answers 0. The answers bubble up from the bottom to the top folder.
How to recognise it
- The input is a binary tree and the answer is one number about its shape.
- The answer for a node can be built from the answers for its two children: depth of a tree = 1 + the deeper child. That is the signature of a bottom-up depth-first search (DFS: follow one branch to the bottom before trying the next).
- "Depth" here counts nodes, not edges: a single node has depth 1, an empty tree 0.
- Up to 10^4 nodes, so visit each node once.
Start with brute force
List every root-to-leaf path, then return the length of the longest one. It follows the definition word for word.
def max_depth_brute(root):
paths = []
def walk(node, path):
if not node:
return
path = path + [node.val] # copy of the path so far
if not node.left and not node.right:
paths.append(path)
walk(node.left, path)
walk(node.right, path)
walk(root, [])
return max((len(p) for p in paths), default=0)
Every node copies the path above it, so time is O(n · h), where h is the height. On a chain of 10^4 nodes that is about 5 × 10^7 copied items, and the stored paths can take O(n · h) memory too. All of that work is only used to read off a length.
From brute force to the idea
- Find the waste. We store whole paths but only need their lengths, and we only need the longest one.
- Ask the children instead. The longest path from a node down is the node itself plus the longest path in whichever subtree is deeper. So
depth(node) = 1 + max(depth(left), depth(right)). - Pick the base case. An empty spot has depth 0. A leaf then gets 1 + max(0, 0) = 1, which is correct with no special case for leaves.
- Return numbers, not lists. Each call returns one integer, so nothing is copied.
This is the key idea: a tree's depth is 1 plus the deeper child's depth, computed bottom-up in one DFS.
The key idea
depth(node) = 1 + max(depth(left), depth(right)). O(n).
Python solution
def max_depth(node):
if not node:
return 0
left = max_depth(node.left)
right = max_depth(node.right)
return 1 + max(left, right)In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · h): each node copies the path above it (O(n²) for a chain) | O(n · h): the stored paths |
| Recursive depth (shown code) | O(n): each node is visited once and does O(1) work | O(h): one stack frame per level, h = n for a chain |
Edge cases
- Empty tree: returns 0.
- Single node: returns 1.
- Chain (every node has one child): returns n; this is the deepest possible tree.
- Very deep tree: a chain of about 1,000 nodes hits Python's default recursion limit and raises
RecursionError, and LeetCode allows up to 10^4 nodes. For full safety use a level-by-level breadth-first search (BFS) and count the levels, or an explicit stack of(node, depth)pairs.
Common mistakes
- Returning 1 for an empty tree, or counting edges instead of nodes, which is off by one.
- Adding the two children's depths instead of taking the larger one; that measures a path through the node (the diameter idea), not depth.
- Reusing this exact code for minimum depth by changing
maxtomin: an empty child then counts as depth 0, so a node with one child looks like a leaf.
Return the minimum depth (LeetCode 111): the number of nodes on the shortest path from the root down to a leaf. For [1, null, 2] the answer is 2, not 1, because the root is not a leaf. Describe your approach, then write it if you like.
Compare with our answer
Keep the bottom-up shape, but an empty child is not a leaf, so it must not win the min. If one child is missing, the path must go through the other child.
def min_depth(root):
if not root:
return 0
if not root.left:
return 1 + min_depth(root.right)
if not root.right:
return 1 + min_depth(root.left)
return 1 + min(min_depth(root.left), min_depth(root.right))
Time O(n), space O(h). A BFS that stops at the first leaf it meets is also good, and it can finish early on a wide tree.
A strong answer mentions: why a missing child cannot count as depth 0, the one-child cases, and that a BFS can stop at the first leaf.
1. You must find how many levels a company org chart has, where each person can have many reports. Which approach fits best?
The same rule works with any number of children: take the maximum over them. Summing counts nodes on many paths, the logarithm only fits a perfectly balanced binary tree, and the first report may not lead to the deepest branch.
2. Why is the shown solution O(n) time?
Both children are always explored (the code cannot know which is deeper until it has looked), and each call does constant work. No caching is involved.
3. A learner turns the shown code into minimum depth by changing max to min. Which input now gets a wrong answer?
The empty left child returns 0, so min picks it and the function returns 1, as if the root were a leaf. Where every node has zero or two children, the empty spots never win, so the other trees still come out right.
Score 60% or more and the lesson is marked complete.