{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Binary Tree Zigzag Level Order Traversal – Solution & Complexity

Interview solutions
/
Binary Tree Zigzag Level Order Traversal

Solution Walkthrough

1. Recognize the Pattern

The key pattern is: BFS processes one queue level at a time while a direction flag decides where each value lands. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(n) — every node is visited once. Space: O(w) for the queue and current level buffer, where w is the widest level of the tree (O(n) worst case).

All 7 languages below implement the same level-order BFS, flipping the write direction after each level.

def zigzag_level_order(root: TreeNode) -> list[list[int]]:
    if root is None:
        return []

    result = []
    queue = [root]
    head = 0
    left_to_right = True

    while head < len(queue):
        level_size = len(queue) - head
        level = [0] * level_size

        for i in range(level_size):
            node = queue[head]
            head += 1
            index = i if left_to_right else level_size - 1 - i
            level[index] = node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)
        left_to_right = not left_to_right

    return result

FAQ

See also

Practice Binary Tree Zigzag Level Order Traversal online (run code in the browser)Binary Tree Level Order Traversal solution (medium)Binary Tree Right Side View solution (medium)Balanced Binary Tree solution (easy)Binary Tree Maximum Path Sum solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?