{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Binary Tree Zigzag Level Order Traversal – Solution & Complexity

Interview solutions
/
Binary Tree Zigzag Level Order Traversal

Solution Walkthrough

  1. Step 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. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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
Learn the Tree Traversal pattern: recognition cues, invariant, and ordered practice →

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 Inorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?