Binary Tree Zigzag Level Order Traversal

Table of Contents +

Reading a tree row by row is a classic. This question adds a twist. You read one row left to right, the next row right to left, then flip again. It looks like a snake moving down the tree. The real test is whether you can flip the order cleanly without making the code messy.

🎯 The Problem

You get a binary tree. Return its values level by level, but flip the reading direction every row.

The rules:

A binary tree is a structure where each node has a value and up to two children.
A level is one row of the tree at the same depth.
The first row reads left to right. The second reads right to left. The third reads left to right again.
This back-and-forth pattern is called zigzag.

Input:
        3
       / \
      9   20
         /  \
        15   7

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

Explanation:
  Row 0 (left to right): 3
  Row 1 (right to left): 20, 9
  Row 2 (left to right): 15, 7

Here is the tree with each row labeled by the direction we read it.

🐢 Approach 1: Collect Rows Then Reverse (Brute Force)

The idea in one line: read every row left to right as usual, then reverse the odd-numbered rows after.

The idea:

Do a normal level by level read. That is level order traversal.
Collect every row left to right.
After a row is done, reverse it if it is an odd-numbered row.

Why it is weak:

Reversing a row with k nodes takes about k steps.
That is an extra pass over half the rows.
It builds the row wrong and then fixes it. A fix-up step you can avoid.

Here is the collect-rows-then-reverse code:

from collections import deque
def zigzag_level_order(root):
    if not root: return []
    q, ans, left = deque([root]), [], True
    while q:
        row = []
        for _ in range(len(q)):
            node = q.popleft(); row.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        ans.append(row if left else row[::-1])
        left = not left
    return ans

⚡ Approach 2: BFS With a Direction Flag (Best)

The idea in one line: build each row in the correct order from the start using one direction flag.

The idea:

Read the tree level by level using BFS, short for breadth-first search.
BFS reads one full row before moving to the next.
It uses a queue, a line where the first one in is the first one out.
Keep one boolean called left_to_right. A boolean is a true or false flag.

How it works:

For each row, build a list of that row’s values.
If the flag is true, append values to the end.
If the flag is false, insert each value at the front. That reverses the row as you build it.
After a row, flip the flag. So the next row reads the other way.
No separate reverse step. The order is correct the moment the row is done.

Why it is clean:

Each node is visited once, so the work is O(n).
A deque per row keeps front inserts cheap.

This diagram shows the flag flipping after each row and steering how values get added.

Steps to Solve

If the tree is empty, return an empty list.
Put the root in a queue. Set a flag left_to_right to true.
While the queue is not empty, find how many nodes are in the current row.
For each node in the row, pop it and read its value.
If the flag is true, add the value to the end of the row list. If false, add it to the front.
Push the node’s children into the queue for the next row.
After the row, add it to the answer and flip the flag.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a deque for BFS and a plain list per row, choosing where to put each value with the direction flag.

from collections import deque


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def zigzag_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True          # direction for the current row
    while queue:
        row_size = len(queue)     # nodes in this row right now
        row = []
        for _ in range(row_size):
            node = queue.popleft()
            if left_to_right:
                row.append(node.val)      # add to the end
            else:
                row.insert(0, node.val)   # add to the front (reverses)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(row)
        left_to_right = not left_to_right  # flip for the next row
    return result


root = Node(3)
root.left = Node(9)
root.right = Node(20)
root.right.left = Node(15)
root.right.right = Node(7)
print(zigzag_level_order(root))

The output of the above code will be:

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

Let us read the Python version line by line, since it shows the direction flip most plainly.

The line if not root: return [] returns early for an empty tree. No tree means no rows.

The line queue = deque([root]) starts the BFS. A deque is a fast queue where you can pop from the front. We seed it with the root.

The line left_to_right = True sets the starting direction. The first row reads left to right.

The line row_size = len(queue) is the key step that keeps rows separate. At this moment the queue holds exactly one full row. So we record how many nodes are in it before we start adding the next row’s children.

The loop for _ in range(row_size) then processes exactly that many nodes. That way children pushed during the loop do not leak into the current row.

Inside, node = queue.popleft() takes the next node from the front, oldest first. That is what makes it BFS.

The if left_to_right block decides where the value goes. row.append adds to the end for a left-to-right row. row.insert(0, node.val) adds to the front, which builds a right-to-left row as you go.

The two if lines push the children for the next row, always left then right.

The line left_to_right = not left_to_right flips the flag after the row. So the next row reads the opposite way. That single flip is the whole zigzag trick.

⏱️ Time and Space Complexity

Every node is visited once, so the base work is O(n). The reverse-after version adds a reverse pass on half the rows, but that is still O(n) overall. The direction-flag version skips the reverse, though insert(0, ...) in a plain list also shifts elements. In practice for interview-sized trees both are fine. The clean choice uses a deque per row, which makes front inserts cheap and keeps it at O(n). Both use O(n) memory for the queue and the answer.

Approach	Time Complexity	Space Complexity
Level order then reverse odd rows	O(n)	O(n)
BFS with direction flag	O(n)	O(n)

Tip

Record the row size before the loop. That one line is what keeps each level separate while you push the next level’s children into the same queue.

🧩 Key Takeaways

✅ Read the tree level by level with BFS using a queue.
✅ Capture the row size before processing, so children do not mix into the current row.
✅ Keep one direction flag and flip it after every row.
✅ When the flag says right to left, add values to the front of the row instead of the end.
✅ A deque per row keeps front inserts cheap, so the whole thing stays O(n).

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Binary Tree Vertical Order Traversal Next All Nodes Distance K in Binary Tree

Binary Tree Zigzag Level Order Traversal

Follow Us

Follow Us