Zigzag Level Walk
Problem
Given the root of a binary tree, collect its values level by level, but alternate the reading direction. The top level is read left to right, the next level right to left, and so on down the tree. Return one list per level, and an empty result for an empty tree.
Examples
Input: tree = 3 with children 9 and 20, where 20 has children 15 and 7
Output: [[3], [20, 9], [15, 7]]
Why: the middle level is reversed, the bottom level returns to normalInput: tree = 1 alone
Output: [[1]]
Why: a single level is read left to rightInput: tree = empty
Output: []
Why: edge case, there are no levels to reportHints
0 / 3
Alternating direction sounds like it changes the traversal, but it only changes how each finished level is presented.
First make sure you can process the tree one complete level at a time, knowing exactly where each level starts and ends.
Use a queue seeded with the root. On each round, note how many nodes are currently queued, since that count is exactly one level. Drain that many nodes, collecting values and queueing their children, then store the collected level forwards or backwards depending on a flag you flip every round.
Solution
A queue drives a standard level-by-level traversal, and the size of the queue at the start of a round is exactly the width of the current level. Draining that many nodes collects one full level while enqueuing the next one. The zigzag is applied only when storing a finished level, reversing it on every other round, so the traversal itself never changes. Time is O(n) and space is O(w) for the widest level.
from collections import deque
class T:
def __init__(self, val, l=None, r=None): self.val, self.left, self.right = val, l, r
def zigzag(root):
if not root: return []
out, q, forward = [], deque([root]), True
while q:
level = []
for _ in range(len(q)): # the current queue size is one full level
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(level if forward else level[::-1])
forward = not forward # flip the reading direction each level
return out
print(zigzag(T(3, T(9), T(20, T(15), T(7))))) # -> [[3], [20, 9], [15, 7]]
print(zigzag(T(1))) # -> [[1]]
print(zigzag(None)) # -> []Stuck on the idea rather than the code? Tree Traversals covers it.