Maximum depth of a tree
We'll cover the following
Find how many levels deep a binary tree goes.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
d11
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Visit 1 at depth 1. Go deep first: push its children, and the left one will be taken next.
max depth 1 · stack [3, 2]
1 / 16
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(h) | Each node is visited once; the stack is as deep as the tree height h. |
In Python
def max_depth(root):
if not root: return 0
return 1 + max(max_depth(root.left), max_depth(root.right))Summary: say it in the interview
- Go as deep as possible before coming back. Recursion does this for you: depth = 1 + max(depth of left, depth of right). Here it is shown with an explicit stack so you can see the order.
- Time O(n), space O(h). Each node is visited once; the stack is as deep as the tree height h.