LeetCode 103 · Queue · BFS

Zigzag Level Order Traversal, explained with a picture

A family photo read like a snake.

Queue · BFS
▶ Watch it step by step

The problem

Return a tree’s values level by level, but alternate direction: left-to-right, then right-to-left, and so on.

Input:  [1, 2, 3, 4, 5, 6, 7]
Output: [[1], [3, 2], [4, 5, 6, 7]]

Picture it

Picture a family photo read like a snake: the first row left to right, the next row right to left. We do a normal level-by-level walk and simply reverse every other row.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

BFS by level; reverse odd levels. O(n).

Python solution

def level_order(root):
    if not root:
        return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            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 len(out) % 2 == 0 else level[::-1])
    return out

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.