429 · N-ary Tree Level Order Traversal

Everything from binary level order (102) still applies — the only change is that a node can enqueue any number of children instead of exactly two.

1 — The problem

An N-ary tree's Node holds a value and a List<Node> of children — zero, one, or many. Level order traversal groups values by depth exactly as in the binary case; the size-snapshot trick from 102 carries over unchanged, because it never actually depended on there being exactly two children. It depended on knowing how many nodes belong to the current level before you start draining the queue — a fact that has nothing to do with fan-out.

2 — Visualizing variable fan-out

Queue<Node> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {    int sz = q.size();    List<Integer> level = new ArrayList<>();    for (int i = 0; i < sz; i++) {        Node nd = q.poll();        level.add(nd.val);        for (Node child : nd.children) q.add(child);    }    result.add(level);}

Node 3 alone contributes two children to the queue in a single dequeue, while 2 and 4 contribute none — the loop for (Node child : nd.children) handles all three cases identically, with no branching on how many children there happen to be.

3 — Complexity and edge cases

• Time: O(n), space: O(n) for the queue in the worst case — identical bounds to the binary version, since every node and every parent-child edge is still touched exactly once.
• A node with many children (a "bushy" root) can make a single level enormous compared to the tree's overall depth — the queue's worst-case size is bounded by the widest level's node count, same as always, just potentially reached in far fewer levels than a binary tree of the same size.
• Empty tree: empty result list.
• A node with an empty children list (rather than null) is the expected representation in most N-ary tree definitions — the for loop simply doesn't execute, no null-check needed, which is actually one line simpler than the binary version's two separate if (left != null) / if (right != null) checks.

4 — Reference implementation

public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            Node nd = q.poll();
            level.add(nd.val);
            for (Node child : nd.children) q.add(child);
        }
        result.add(level);
    }
    return result;
}