// Binary Tree Level Order Traversal

task

Given the root of a binary tree, return its level order traversal: a list of lists, one inner list per depth, values left to right. LeetCode #102 — the first tree problem in this book, so the node type is worth writing out in full.

    3
   / \
  9  20
     / \
    15  7

level order → [[3], [9, 20], [15, 7]]

how to think

Every traversal so far in this pattern has walked a flat structure with a queue; a tree is just a graph where “neighbors” means .Left and .Right instead of grid offsets or an adjacency list. The one thing level order needs that plain BFS doesn’t give you for free is the level boundary — not just every node in queue order, but every node grouped by depth.

The trick: before draining the queue for real, snapshot queue.Count. That number is exactly how many nodes belong to the current level, because everything currently in the queue was enqueued by the previous level and nothing else has been added yet. Process exactly that many, and whatever gets enqueued along the way becomes next level’s batch — never mixed into this one.

solution

public IList<IList<int>> LevelOrder(TreeNode? root)
{
    var result = new List<IList<int>>();
    if (root is null) return result;

    Queue<TreeNode> queue = new();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        int size = queue.Count;                 // everyone currently queued belongs to this level
        var level = new List<int>();

        for (int i = 0; i < size; i++)
        {
            TreeNode node = queue.Dequeue();
            level.Add(node.Val);

            if (node.Left is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
        result.Add(level);
    }
    return result;
}

// standard interview definition
public class TreeNode(int val = 0, TreeNode? left = null, TreeNode? right = null)
{
    public int Val = val;
    public TreeNode? Left = left;
    public TreeNode? Right = right;
}

trace

    3
   / \
  9  20
     / \
    15  7

Queue is empty after round 2 — loop ends. result = [[3], [9, 20], [15, 7]].

why it works

The invariant is the whole proof: size = queue.Count, captured once per round, always equals exactly the nodes at the current depth. That holds by induction — round 0 starts with just the root (depth 0, count 1); every node dequeued during round k enqueues only its children, which are depth k+1, so by the time round k finishes, the queue holds exactly the depth-(k+1) nodes and nothing else. Grabbing queue.Count before the inner loop starts is what keeps this round’s dequeues from also draining next round’s enqueues.

common bugs

• Reading queue.Count inside the inner for loop instead of snapshotting it once before — after the first Enqueue the count changes, the loop bound drifts, and levels bleed into each other.
• Forgetting the root is null guard — enqueueing a null root either throws or corrupts every dequeue after it.
• Dequeuing without checking node.Left/node.Right for null before enqueueing them — crashes on any leaf.
• Reaching for DFS with a depth parameter and grouping by depth afterward — it works, but it’s the wrong tool: BFS gives you the grouping for free, in the order you want it in.

variant: right side view

Same BFS, same level-boundary trick — the only change is what you keep from each round. The rightmost node at each depth is whichever one gets dequeued last in that round, so instead of collecting every value, keep only the one at i == size - 1:

public IList<int> RightSideView(TreeNode? root)
{
    var result = new List<int>();
    if (root is null) return result;

    Queue<TreeNode> queue = new();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        int size = queue.Count;
        for (int i = 0; i < size; i++)
        {
            TreeNode node = queue.Dequeue();
            if (i == size - 1) result.Add(node.Val);   // last dequeue this round = rightmost at this depth

            if (node.Left is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
    }
    return result;
}

On the same tree this returns [3, 20, 7] — round 0’s only node, round 1’s last dequeue (20, not 9), round 2’s last dequeue (7). LeetCode #199, a one-line change to a template you already trust, beats writing a new recursive DFS-with-depth-tracking solution from scratch.

variants you can now solve

• Average of Levels in Binary Tree (LC 637) — same round loop, average level instead of returning it raw.
• N-ary Tree Level Order Traversal (LC 429) — identical shape, node.Children replaces .Left/.Right.
• Maximum Depth of Binary Tree (LC 104) — depth is just result.Count here; that page solves it with postorder DFS instead.
• Binary Tree Zigzag Level Order Traversal (LC 103) — alternate level.Add and level.Insert(0, ...) per round.