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

Group a binary tree by depth, preserving structural left-to-right order. A list traversal order is not enough unless the result also retains the boundary between levels.

Rescanning once per depth repeats visits, especially on a long chain. A queue keeps one frontier; capturing its size before processing prevents newly appended children from being consumed in the same level.

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.

A queue separates frontier order from recursion depth. Capture the current queue size before visiting a level; adding children while iterating that fixed count preserves level boundaries and left-to-right order. Null children must not enter ArrayDeque. Final O(n) time and O(w) frontier space, excluding output.

A fixed frontier size remains meaningful even as the queue grows with the next depth:

import java.util.*;

class Example {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>(List.of("left", "right"));
        int levelSize = queue.size();
        queue.addLast("left.child");
        assert levelSize == 2;
        assert queue.size() == 3;
    }
}

The current level still contains two nodes. Iterating until the queue becomes empty would merge all later depths into the same output level. ArrayDeque rejects null, so child checks belong before enqueueing.

A wide bracket needs queue space

Frontier processing supports level summaries, tree visualization, and breadth-limited exploration. Space tracks maximum frontier width; a deep narrow tree can use little queue space even with many total nodes.

Input is null or a finite tree of immutable Tree records with unique names and no shared children. Return one fresh list per depth, in structural left-to-right order. Null input returns an empty list.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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