AI Hints
DSA in Python · Lesson 63 of 132

Level Order

Breadth first.

⏱ 2 min read▶ Video at 1:14:12🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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 Order
From the video: Level Order
  • 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.

levels.pypython
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()))
Output
[[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.

keyvalue
DFSstack or recursion
BFSqueue
Nearest firstBFS
Explore everythingeither

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
Next up: Tree Size and Height — recursive measurements