Binary trees and level-order traversal

A tournament viewer stores the final match at the root of a binary bracket, with earlier matches underneath it. The display needs the final first, then its semifinals together, then the next round. Following one branch to the bottom would mix those rows.

Level-order traversal keeps the next row in a queue. The match labels don't need sorting; their left-to-right order comes from the bracket itself.

Displaying a bracket one round at a time

A breadth-first frontier contains nodes at exactly one depth. Snapshot the queue's current size before processing the level; children appended during that loop belong to the next level. Iterating until the queue empties inside a level would flatten the whole tree.

Keeping children in the next frontier

With root a, children b, c, and d beneath b, the rows are [a], [b, c], and [d]. Snapshot the queue length before processing a row. When processing b adds d, that new child must wait for the next row rather than extend the current one. A missing child contributes no placeholder label.

std::queue<const Tree*> q;
if(root) q.push(root.get());
auto level_size=q.size(); // freeze this before enqueueing children

A wide bracket needs queue space

Push left before right to preserve structural order. Names are data, not sort keys. The queue holds observer pointers while the input tree's shared owners keep allocations alive. This lesson uses shared_ptr solely to make recursive test fixtures easy to construct and copy; the documented input still has no shared children or cycles. Do not mutate nodes or ownership links. Each node enters once, giving O(n) traversal and O(w) auxiliary memory for the maximum frontier width. Repeated depth scans are an intentionally slower prototype.

A queue traversal visits each of n nodes once. Its working frontier uses O(w) space for maximum width w, while returned rows contain O(n) labels. Rewalking from the root for every depth can become O(n²) on a chain. Depth-first traversal may suit subtree computations better.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

The bracket stores a tree; a shared or cyclic match graph would also need discovery tracking.