Level order traversal
We'll cover the following
Visit a binary tree level by level, left to right.
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.
8
4
12
2
6
10
14
1
3
5
7
9
11
13
15
Take 8 off the front of the queue and visit it. Add its children (4, 12) to the back.
queue [4, 12] · order [8]
1 / 15
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(w) | Each node is queued once; w = the widest level. |
In Python
from collections import deque
def level_order(root):
q, out = deque([root]), []
while q:
node = q.popleft()
out.append(node.val)
for kid in (node.left, node.right):
if kid: q.append(kid)
return outSummary: say it in the interview
- A queue is first in, first out. Visit a node, then add its children to the back. Everything on one level is visited before anything deeper.
- Time O(n), space O(w). Each node is queued once; w = the widest level.