Binary Tree ZigZag level order traversal

Problem Link

Binary Tree Zigzag Level Order Traversal – LeetCode

Problem: Binary Tree Zigzag Level Order Traversal

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values.
(i.e., from left to right, then right to left for the next level, and alternate between).

Examples

Example 1

Input:

        3
       / \
      9  20
         / \
        15  7

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

Example 2

Input: root = [1]
Output: [[1]]

Example 3

Input: root = []
Output: []

Constraints

• The number of nodes in the tree is in the range [0, 2000]

• -100 <= Node.val <= 100

Intuition

This is a variation of level-order traversal (BFS) in a binary tree.
The only difference is that alternate levels are traversed right to left instead of left to right.

To implement the zigzag pattern, we can:

• Traverse level by level using a queue (BFS).

• At each level:

  • Maintain a list for the current level values.

  • If it's an odd-numbered level, reverse the list before adding to result (or use LinkedList and insert at front).

• Toggle a leftToRight boolean at each level.

Approach

1. Use a Queue<TreeNode> to perform BFS.

2. Use a boolean flag leftToRight to determine the direction for each level.

3. For each level:

   • Create a temporary list of that level's values.

   • If leftToRight is true, add values as is.

   • If false, insert values at the beginning or reverse list later.

4. Add the level list to the result.

5. Toggle leftToRight after each level.

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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 leftToRight = true;

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

            for(int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();

                if(leftToRight) {
                    level.addLast(curr.val);
                } else {
                    level.addFirst(curr.val);
                }

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

            result.add(level);
            leftToRight = !leftToRight; // Toggle direction
        }

        return result;
    }
}

Time and Space Complexity

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

• Space Complexity: O(N)
  Space for queue and result list.

Dry Run

Input:

        1
       / \
      2   3
     / \   \
    4   5   6

Level 0 → [1] (left to right)
Level 1 → [3, 2] (right to left)
Level 2 → [4, 5, 6] (left to right)

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

Conclusion

This problem is a simple extension of level-order traversal. It demonstrates:

• Queue-based BFS traversal.

• Alternating direction control using a flag.

• Efficient use of LinkedList for directional insertions.