Zigzag Level Order Traversal

Interview Problem Interview Medium Binary Tree Queue Breadth-first Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.zigzagLevelOrder(root). Return node values level by level, left-to-right on the first level and alternating direction afterward.

Starter code

class Solution:
    def zigzagLevelOrder(self, root):
        pass

Test cases

three-levels

{
  "args": [
    {
      "$type": "binary-tree",
      "values": [
        3,
        9,
        20,
        null,
        null,
        15,
        7
      ]
    }
  ]
}

Expected: [[3],[20,9],[15,7]]

Wizard outline

Step 1: Initialize Solution.zigzagLevelOrder
Replace the empty starter with the first real state owned by Solution.zigzagLevelOrder. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Empty case
Complete the readable core algorithm for one representative Interview case. Keep BFS child enqueue order stable and reverse only the collected level values.
Step 3: Harden the Three Levels boundary
Repair the reviewed boundary and pass the complete submission contract. BFS groups exactly equal-depth nodes in natural left-to-right order. Reversing precisely odd levels implements the required alternating presentation without affecting later traversal.

Footguns and prerequisites

Reversing child enqueue order changes the traversal structure and complicates the next level.
trees and graphs

Reviewed references

LeetCode 103 — Binary Tree Zigzag Level Order Traversal

Practice prerequisites

Expand One Tree Level(opens in a new tab)
Expand One Tree Level isolates at the start of each outer iteration, the queue contains exactly the current level in left-to-right order. That focused state discipline is required when implementing zigzag level order as a complete Interview Problem.

Recommended approach and implementation

Standard BFS by fixed level size; collect values left-to-right, reverse the list on odd-numbered levels, and always enqueue left then right.

Why it works: BFS groups exactly equal-depth nodes in natural left-to-right order. Reversing precisely odd levels implements the required alternating presentation without affecting later traversal.

class Solution:
    def zigzagLevelOrder(self, root):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if root is None: return []
        from collections import deque
        queue = deque([root])
        output = []
        left_to_right = True
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            output.append(level if left_to_right else level[::-1])
            left_to_right = not left_to_right
        return output

Similar exercises

Binary Tree Level Order(opens in a new tab)