Step 4 of 6

Level order with a queue

Breadth-first traversal visits a tree level by level. Instead of recursion it uses a queue: take a node from the front, record it, push its children to the back. The same technique finds shortest paths in graphs (next module).

To separate the levels, process the queue in batches: at the start of each level, the queue holds exactly that level's nodes.

while (!q.empty()) {
    std::size_t n = q.size();      // nodes on this level
    for (std::size_t i = 0; i < n; i++) { ... q.pop(); push children ... }
}

Your turn: write std::vector<std::vector<int>> levels(const Node* root).

Previous: Traversals and validation Next: A binary heap by hand