Zigzag level order traversal

Breadth-first, but alternate the reading direction of every level, left-to-right then right-to-left.

The idea

Run an ordinary level-order BFS with a queue, but keep a flag that flips after every level. On a left-to-right level, place each dequeued node at the next free index; on a right-to-left level, place it counting down from the end instead. Enqueueing children always happens in the same left-then-right order; only where each value lands in the level's array changes.

Code

public static List<List<int>> ZigzagLevelOrder(TreeNode root) {
    var result = new List<List<int>>();
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    bool leftToRight = true;
    while (queue.Count > 0) {
        int count = queue.Count;
        var level = new int[count];
        for (int i = 0; i < count; i++) {
            TreeNode node = queue.Dequeue();
            int idx = leftToRight ? i : count - 1 - i;
            level[idx] = node.val;
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
        result.Add(level.ToList());
        leftToRight = !leftToRight;
    }
    return result;
}

Tips

• The queue itself never reverses. Only the index each value is written to changes, which is cheaper than reversing a completed list.

In the .NET library

This is plain level order traversal with one extra piece of bookkeeping (the alternating flag), proof that fiddly-looking output requirements rarely need a different traversal, just different handling of the same visit order.