Level Order Traversal
Trees & BST: lesson 9 of 14
A queue turns a tree into one tidy row per depth.
Lesson 9 of 14 · 5 min
Level Order Traversal
Step 1 of 10
level0queued1
queue — front on the left
3
One node in the queue: the root. Everything else follows from take the front, push its children.
The Idea
Push the root, then repeatedly take the front node and push its children. That is breadth-first order — everything at depth 1, then everything at depth 2.
To get one list per level, read the queue's length before the loop. Whatever is in there right now is exactly this level.
Real-World Example
A phone tree where every person rings their two contacts. Everyone one call away learns the news before anyone two calls away, no matter which branch they are on.
The Code
from collections import deque
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def levels(root):
out, q = [], deque([root])
while q:
row = []
for _ in range(len(q)): # exactly the nodes standing on this level
n = q.popleft()
row.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
out.append(row) # one list per level, depth for free
return out
print(levels(Node(3, Node(9), Node(20, Node(15), Node(7))))) # [[3], [9, 20], [15, 7]]Your turn
Fill in the blank.
from collections import deque
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
root = Node(3, Node(9), Node(20, Node(15), Node(7)))
out, q = [], deque([root])
while q:
row = []
for _ in range(___):
n = q.popleft()
row.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
out.append(row)
print(out) # should print [[3], [9, 20], [15, 7]]Mini quiz
1 / 3