Step 4 of 6

Level order with a queue

Depth-first orders dive down one branch before trying the next. Breadth-first traversal instead visits a tree level by level: the root, then all its children, then all their children. Instead of recursion it uses a queue:

1. Put the root in the queue.
2. Take the node at the front, handle it, and push its children to the back.
3. Repeat until the queue is empty.

Because children join at the back, every node of one level is handled before any node of the next.

To separate the levels, process the queue in batches: at the start of each round, the queue holds exactly one level's nodes, so remember q.size() and pop exactly that many.

#include <iostream>
#include <memory>
#include <queue>
#include <string>
#include <vector>

struct Emp {
    std::string name;
    std::vector<std::unique_ptr<Emp>> reports;    // any number of children
};

std::unique_ptr<Emp> emp(std::string n) { return std::make_unique<Emp>(Emp{std::move(n), {}}); }

int main() {
    auto ceo = emp("Ava");
    ceo->reports.push_back(emp("Ben"));
    ceo->reports.push_back(emp("Cy"));
    ceo->reports[0]->reports.push_back(emp("Dee"));
    ceo->reports[1]->reports.push_back(emp("Eli"));
    ceo->reports[1]->reports.push_back(emp("Fay"));

    std::queue<const Emp*> q;
    q.push(ceo.get());
    int level = 0;
    while (!q.empty()) {
        std::size_t n = q.size();                  // everyone on this level
        std::cout << "level " << level++ << ":";
        for (std::size_t i = 0; i < n; i++) {
            const Emp* e = q.front();
            q.pop();
            std::cout << " " << e->name;
            for (const auto& r : e->reports) q.push(r.get());
        }
        std::cout << "\n";
    }
}

level 0: Ava
level 1: Ben Cy
level 2: Dee Eli Fay

Details

• The queue holds plain const Emp* pointers. It doesn't own anything; the tree does.
• Children are pushed while the current level is being processed, but they sit behind the current level's nodes, and the saved count n stops the inner loop before reaching them.
• An empty tree (a null root) should return an empty result, so check before pushing it.

The same technique finds shortest paths in graphs, as you'll see in the next module: breadth-first order reaches every node by the fewest possible steps.

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

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