Zigzag Level Order Traversal in Java: A Simple and Clear Guide

Working with binary trees can be exciting, especially when you encounter traversal problems that require a little twist.

One such problem is Zigzag Level Order Traversal, where you don’t simply traverse each level from left to right—you need to alternate directions on each level.

In this post, I’ll walk you through the solution using Java, provide step-by-step explanations, and share some helpful insights to make the concept stick.

📝 Problem Overview

The task is to traverse a binary tree level by level, but the direction switches at each level.

• First level: left to right
• Second level: right to left
• Third level: left to right
• And so on…

This creates a zigzag or spiral-like pattern.

📊 Example

Given the following tree:

        1
       / \
      2   3
     / \   \
    4   5   6

Expected Output:

[
  [1],
  [3, 2],
  [4, 5, 6]
]

💡 Thought Process

We can approach this using Breadth-First Search (BFS) with a small twist:

• Keep track of whether we should read left-to-right or right-to-left.
• Use a LinkedList to allow quick insertions at both the beginning and end.
• Flip the direction after processing each level.

✅ Java Solution

Here’s a clean and readable Java implementation:

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        boolean isLeftToRight = true;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            LinkedList<Integer> levelList = new LinkedList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();

                if (isLeftToRight) {
                    levelList.addLast(currentNode.val);
                } else {
                    levelList.addFirst(currentNode.val);
                }

                if (currentNode.left != null) queue.offer(currentNode.left);
                if (currentNode.right != null) queue.offer(currentNode.right);
            }

            result.add(levelList);
            isLeftToRight = !isLeftToRight; // Flip direction for the next level
        }

        return result;
    }
}

🔍 Step-by-Step Breakdown

Initialization:

• Use a Queue for standard BFS.
• Set a boolean flag isLeftToRight to track the traversal direction.

Processing Each Level:

• For every level, traverse all nodes in the queue.
• Add node values to the front or back of the level list based on the current direction.

Queue Management:

• Always add child nodes to the queue to prepare for the next level.

Switch Direction:

• After finishing a level, simply flip the boolean flag.

🕐 Time and Space Complexity

• Time Complexity: O(N)
  
  Every node is visited once.

• Space Complexity: O(N)
  
  The queue and the output list together may hold all nodes.

🚀 Quick Takeaways

• Zigzag traversal is just a variation of level order traversal.
• Keeping track of traversal direction is key.
• Picking the right data structure (like LinkedList) simplifies the solution.

🔗 Related LeetCode Problems

• Binary Tree Level Order Traversal
• Binary Tree Zigzag Level Order Traversal
• Binary Tree Right Side View

🙌 Final Thoughts

This problem is a great example of how small tweaks can make a standard algorithm interesting.

If you’re diving into tree problems, this is a solid pattern to learn and reuse.

Feel free to drop your thoughts, suggestions, or questions!

Also, I’d love to connect if you’re interested in exploring more DSA problems together. 🚀