174. Zigzag Level Order

Why this mechanism works

Separate visitation order from presentation order. Collect every level with the reliable FIFO protocol, then reverse only the completed list for odd-numbered depths. Changing queue direction and child insertion together is unnecessary and creates more cases to reason about.

State and boundaries

levels is ordinary left-to-right level order. Index depth determines whether that complete output group is reversed.

Protocol

1. Obtain the level groups using kata 171.
2. Visit odd-numbered level indices.
3. Reverse each such list in place.
4. Return the groups.

Visualization

BFS groups: [1] [2,3] [4,5,6]
directions:   ->   <-       ->
output:     [1] [3,2] [4,5,6]

Python implementation

from kata_171 import level_order
from structures import build_tree

def zigzag_levels(root):
    levels = level_order(root)
    for depth in range(1, len(levels), 2):
        levels[depth].reverse()
    return levels

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 zigzag_levels: levels = level_order(root)
root=N1(val=1,left=N2,right=N3); levels=[[1], [2, 3], [4, 5, 6]]

L6 zigzag_levels: for depth in range(1, len(levels), 2):
root=N1(val=1,left=N2,right=N3); levels=[[1], [2, 3], [4, 5, 6]]; depth=1

L7 zigzag_levels: levels[depth].reverse()
root=N1(val=1,left=N2,right=N3); levels=[[1], [3, 2], [4, 5, 6]]; depth=1

L5 zigzag_levels: levels = level_order(root)
root=None; levels=[]

Why the solution is correct

Kata 171 produces the correct nodes for every depth in left-to-right order. Reversing exactly the odd-depth lists changes only their presentation direction and preserves membership. Even-depth groups remain unchanged, satisfying the alternating contract.

Time and space

O(n) time including all reversals, O(n) output space and O(w) BFS auxiliary queue space inherited from kata 171.

Common mistakes

Reversing the whole flattened output changes level order. Mutating traversal mechanics is unnecessary when only emitted order must change.

Reasoning card

Transfer exercise

Write a streaming version that yields one completed level at a time instead of retaining every group.