Hey everyone! 👋
In this blog, we will explore the Zigzag Level Order Traversal of a binary tree – a very common interview question that challenges your understanding of Breadth-First Search (BFS) and how to modify it for custom traversal patterns.

Let’s dive into the problem step by step! 🚀

📄 Problem Description

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values.
(First level from left to right, second level from right to left, third from left to right, and so on.)

📚 Example Input and Output

Input:

Output:

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

Explanation:

Level 1: Traverse left to right → [1]
Level 2: Traverse right to left → [3, 2]
Level 3: Traverse left to right → [4, 5, 6]

🧠 Intuition

This problem is a variation of standard BFS traversal.
Normally, we traverse each level from left to right.
In this problem, we need to reverse the direction on every alternate level.

How do we handle this?
We can use:

A queue for BFS.
A flag (boolean variable) to track whether we should insert nodes from left to right or right to left.
A LinkedList (or Deque) to efficiently add elements at the beginning or end of the list based on the direction.

✅ Java Solution

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

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

        boolean reverse = false;

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

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

                if (reverse) levelList.addFirst(node.val);
                else levelList.addLast(node.val);

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            ans.add(levelList);
            reverse = !reverse; // switch direction for next level
        }

        return ans;
    }
}

🔍 Step-by-Step Explanation

Step 1: Initialize Data Structures

Queue<TreeNode> queue: Used for BFS traversal.
boolean reverse = false: Keeps track of whether we should insert from left to right or right to left.
List<List<Integer>> ans: Final answer list.

Step 2: Level-by-Level Traversal

Use a while loop until the queue is empty (means all nodes are processed).
For each level:
- Determine the number of nodes at the current level (levelSize).
- Use a LinkedList<Integer> to store nodes of the current level.

Step 3: Insert Node Values in the Correct Order

If reverse is false: Insert at the end (normal BFS order).
If reverse is true: Insert at the beginning (reverses the order).

Step 4: Add Child Nodes to the Queue

Always add the left child (if exists) and the right child (if exists) to the queue to process them in the next level.

Step 5: Flip the Direction

After completing a level, flip the reverse flag so the next level is traversed in the opposite direction.

📚 Detailed Example Walkthrough

Let's walk through the example tree:

Level 1:

Queue: [1]
Direction: Left to Right
Output: [1]

Level 2:

Queue: [2, 3]
Direction: Right to Left
Output: [3, 2]

Level 3:

Queue: [4, 5, 6]
Direction: Left to Right
Output: [4, 5, 6]

Final Output:

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

🛠 Time and Space Complexity

Time Complexity: O(N)
We visit each node exactly once.
Space Complexity: O(N)
The queue and the result list together take O(N) space.

💡 Key Takeaways

This is a classic BFS problem with a twist.
Using a boolean flag is a great pattern for handling alternating behaviors.
Always think about the most efficient data structure. LinkedList was key here because of its ability to add elements quickly at both ends.

✨ Final Thoughts

Zigzag traversal is a great problem to practice tree traversal variations.
Try tweaking this solution to support custom traversal orders or adding a depth tracker!

If you enjoyed this post or found it helpful, let’s connect! Feel free to reach out with any questions or share your own approach! 🚀

🔖 Tags:

#LeetCode #BinaryTree #Java #CodingInterview #DSA #ZigzagTraversal #100DaysOfCode #OpenSource

🌳 LeetCode: Zigzag Level Order Traversal – Complete Guide with Java Solution and Examples