Binary Tree Zigzag Level Order Traversal

Master this topic with zero to advance depth.

Binary Tree Zigzag Level Order Traversal

Zigzag BFS.

Medium

Approach 1

Level I: BFS + Reverse

Intuition

Process the tree level by level using a queue (standard BFS). After gathering all nodes for a specific level, check if the level index is odd. If it is, reverse the list of values before adding it to the final result.

Thought Process

Standard BFS.
Maintain levelIndex starting at 0.
Collect level nodes.
If levelIndex % 2 != 0, reverse level list.
Increment levelIndex.

⏱ O(N)💾 O(N)

Detailed Dry Run

Level	Nodes	Reverse?	State
0	[3]	No	[[3]]
1	[9, 20]	Yes	[[3], [20, 9]]
2	[15, 7]	No	[[3], [20, 9], [15, 7]]

java

import java.util.*;

public class Main {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean reverse = false;
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            if (reverse) Collections.reverse(level);
            res.add(level);
            reverse = !reverse;
        }
        return res;
    }
}

Approach 2

Level II: Two Stacks

Intuition

Instead of reversing level results after-the-fact, we can use two stacks to maintain the order. One stack processes Left-to-Right, and the other Right-to-Left. As we pop from one stack, we push its children into the other stack in an order that keeps the next level correctly oriented.

Logic

Stack1 (L to R): Push Left child, then Right child to Stack2.
Stack2 (R to L): Push Right child, then Left child to Stack1.

⏱ O(N)💾 O(N)

Detailed Dry Run

S1: [3]. Pop 3, S2: [9, 20]. Pop 20, S1: [7, 15]. Pop 9... result levels built directly in order.

java

public class Main {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty() || !s2.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            if (!s1.isEmpty()) {
                while (!s1.isEmpty()) {
                    TreeNode node = s1.pop();
                    level.add(node.val);
                    if (node.left != null) s2.push(node.left);
                    if (node.right != null) s2.push(node.right);
                }
            } else {
                while (!s2.isEmpty()) {
                    TreeNode node = s2.pop();
                    level.add(node.val);
                    if (node.right != null) s1.push(node.right);
                    if (node.left != null) s1.push(node.left);
                }
            }
            res.add(level);
        }
        return res;
    }
}

Approach 3

Level III: Optimal (BFS + Double-Ended Queue)

Intuition

Thought Process

Directly inserting at either the head or tail of a Deque based on the current level's direction avoids the need for an explicit Reverse step. This is more efficient as we determine the correct spot for each node exactly once.

Logic

Use a standard BFS queue.
For each level, initialize an empty Deque.
If LevelIndex is even: Add to the back (tail).
If LevelIndex is odd: Add to the front (head).

Complexity

Time: $O(N)$
Space: $O(N)$ (Queue size)

⏱ O(N)💾 O(N)

Detailed Dry Run

Level	Node	Direction	Deque State
1	9	Left to Right	[9]
1	20	Left to Right	[9, 20]
2	15	Right to Left	[15]
2	7	Right to Left	[7, 15]

java

public class Main {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean leftToRight = true;
        while (!q.isEmpty()) {
            int size = q.size();
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (leftToRight) level.addLast(node.val);
                else level.addFirst(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            res.add(level);
            leftToRight = !leftToRight;
        }
        return res;
    }
}

⚠️ Common Pitfalls & Tips

While unshift in JS or appendleft in Python is $O(1)$ for Deques, using them on standard arrays can be $O(N)$ per operation. Be sure to use appropriate data structures.

← Previous QuestionLowest Common Ancestor of a Binary Tree

Next Question →Path Sum II

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.