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 task

Write std::vector<std::vector<int>> levels(const Node* root).

Challenge 2

Write std::vector<int> right_view(const Node* root): the key you would see on each level looking at the tree from the right, which is the last node of each level in breadth-first order.

Challenge 3

Write int min_depth(const Node* root): the number of nodes on the shortest path from the root down to a leaf (0 for an empty tree). Use breadth-first search, which can stop at the first leaf it reaches instead of exploring the whole tree.

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