Level Order
Breadth first.
Sometimes you want to visit a tree level by level. The root first, then all of its children, then all of their children. That's breadth first traversal, and it uses a queue.

- Level by level
- Root, children, grandchildren
- Uses a queue
Breadth first with a queue
We put the root in a queue. Then, while the queue has nodes, we take one from the front, record it, and add its children to the back. Because a queue is first in, first out, nodes come out level by level. Here we also group them by level. Run it.
from collections import deque
from tree import sample
def levels(root):
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.value)
queue.extend(c for c in (node.left, node.right) if c)
result.append(level)
return result
print(levels(sample()))[[8], [3, 10], [1, 6, 14], [4, 7, 13]]
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'Depth first or breadth first?
Depth first uses recursion, or a stack, and goes deep quickly. Breadth first uses a queue, and finds things close to the root first. So if you want the nearest match, or the shortest path, breadth first is usually the answer. We'll use this again with graphs.
| key | value |
|---|---|
| DFS | stack or recursion |
| BFS | queue |
| Nearest first | BFS |
| Explore everything | either |
Summary
Breadth first traversal uses a queue to visit a tree level by level. Next, measuring trees with recursion.
Key takeaways- Queue the root
- Pop, record, add children
- Level by level