Zigzag Level Order Traversal in DSA Java - Build from Scratch

Zigzag Level Order Traversal

📖 Scenario: You are working with a binary tree data structure that stores numbers. You want to visit the nodes level by level, but in a zigzag pattern: the first level from left to right, the second level from right to left, then the third level from left to right again, and so on.This pattern helps in some real-world cases like printing hierarchical data in a visually interesting way or processing tree data with alternating directions.

🎯 Goal: Build a Java program that performs a zigzag level order traversal on a binary tree and prints the values level by level in the zigzag order.

📋 What You'll Learn

Create a binary tree with the exact nodes given

Use a variable to track the current traversal direction

Implement the zigzag level order traversal logic using a queue and direction flag

Print the final list of levels with nodes in zigzag order

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in visualizing hierarchical data with alternating directions, such as organizational charts or tree-based UI components.

💼 Career

Understanding tree traversals and queue usage is important for software engineering roles involving data structures, algorithms, and system design.

1

Create the binary tree nodes

Create a class called TreeNode with an integer val, and two TreeNode references called left and right. Then create the root node called root with value 1. Add left child with value 2 and right child with value 3 to the root. Add left child with value 4 and right child with value 5 to the node with value 2. Add right child with value 6 to the node with value 3.

DSA Java

// Define TreeNode class and create the binary tree nodes as described
// Your code here

Hint

Define the TreeNode class first, then create the nodes exactly as described.

2

Add a direction flag for zigzag traversal

Inside the main method, create a boolean variable called leftToRight and set it to true. This variable will track the current direction of traversal for each level.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        // Create a boolean variable called leftToRight and set it to true
        // Your code here
    }
}

Hint

Use boolean leftToRight = true; inside the main method.

3

Implement zigzag level order traversal logic

Inside the main method, implement the zigzag level order traversal using a Queue<TreeNode> called queue. Add the root node to the queue. Create a List<List<Integer>> called result to store the levels. Use a while loop to process nodes level by level. For each level, create a LinkedList<Integer> called levelList. Iterate over the nodes in the current level. If leftToRight is true, add node values to the end of levelList. If false, add node values to the front of levelList. Add children of nodes to the queue for the next level. After processing each level, add levelList to result and toggle leftToRight to its opposite value.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        boolean leftToRight = true;

        // Implement zigzag level order traversal using queue and leftToRight
        // Your code here
    }
}

Hint

Use a queue to process nodes level by level. Use a LinkedList to add values at front or end depending on leftToRight. Toggle leftToRight after each level.

4

Print the zigzag level order traversal result

After the traversal loop, print the result list to display the zigzag level order traversal. Use System.out.println(result); inside the main method.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        boolean leftToRight = true;

        Queue queue = new LinkedList();
        queue.add(root);
        List> result = new ArrayList();

        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList levelList = new LinkedList();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    levelList.addLast(node.val);
                } else {
                    levelList.addFirst(node.val);
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(levelList);
            leftToRight = !leftToRight;
        }

        // Print the result list
        // Your code here
    }
}

Hint

Use System.out.println(result); to print the final zigzag traversal list.

Practice

1. What is the main difference between a normal level order traversal and a zigzag level order traversal of a binary tree?

easy

A. Zigzag traversal alternates the direction of node visits at each level.

B. Zigzag traversal visits nodes only on odd levels.

C. Zigzag traversal visits nodes in reverse order at all levels.

D. Zigzag traversal visits nodes randomly without any order.

Solution

1. Step 1: Understand normal level order traversal

   Normal level order traversal visits nodes level by level from left to right.

2. Step 2: Understand zigzag traversal difference

   Zigzag traversal changes direction at each level, alternating between left-to-right and right-to-left.

3. Final Answer:

   Zigzag traversal alternates the direction of node visits at each level. -> Option A

4. Quick Check:

   Zigzag = alternate direction [OK]

Hint: Remember zigzag flips direction every level [OK]

Common Mistakes:

• Thinking zigzag visits only odd levels
• Assuming zigzag always goes right to left
• Confusing zigzag with random order

2. Which of the following Java code snippets correctly initializes a queue for level order traversal?

easy

A. Queue<TreeNode> queue = new ArrayList<>();

B. Queue<TreeNode> queue = new HashSet<>();

C. Queue<TreeNode> queue = new Stack<>();

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

Solution

1. Step 1: Identify correct queue implementation

   Java's Queue interface is commonly implemented by LinkedList for FIFO behavior.

2. Step 2: Check other options

   ArrayList is a list, not a queue; Stack is LIFO, not queue; HashSet is a set, no order.

3. Final Answer:

   Queue<TreeNode> queue = new LinkedList<>(); -> Option D

4. Quick Check:

   Queue = LinkedList [OK]

Hint: Use LinkedList for queue in Java [OK]

Common Mistakes:

• Using ArrayList instead of Queue
• Using Stack which is LIFO, not FIFO
• Using HashSet which has no order

3. Given the binary tree below, what is the zigzag level order traversal output?

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Traverse level 0 left to right

   Level 0 nodes: [1]

2. Step 2: Traverse level 1 right to left

   Level 1 nodes: [2, 3] reversed to [3, 2]

3. Step 3: Traverse level 2 left to right

   Level 2 nodes: [4, 5, 6]

4. Final Answer:

   [[1], [3, 2], [4, 5, 6]] -> Option A

5. Quick Check:

   Zigzag levels alternate direction [OK]

Hint: Alternate direction each level starting left to right [OK]

Common Mistakes:

• Not reversing nodes on odd levels
• Reversing nodes on even levels incorrectly
• Mixing node order at last level

4. Consider the following Java code snippet for zigzag traversal. What is the error?

Queue<TreeNode> queue = new LinkedList<>();
boolean leftToRight = true;
while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> level = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        if (leftToRight) level.add(node.val);
        else level.add(0, node.val);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    leftToRight = !leftToRight;
}

medium

A. The boolean flag leftToRight should not be toggled.

B. The queue should be a Stack for zigzag traversal.

C. The for loop condition should be i < size, not i <= size.

D. The level list should be a LinkedList instead of ArrayList.

Solution

1. Step 1: Analyze for loop condition

   The loop runs from i = 0 to i <= size, which means it runs size+1 times, causing poll() to return null once.

2. Step 2: Correct loop condition

   The loop should run exactly size times, so condition must be i < size.

3. Final Answer:

   The for loop condition should be i < size, not i <= size. -> Option C

4. Quick Check:

   Loop runs size times [OK]

Hint: Use i < size for loops over queue size [OK]

Common Mistakes:

• Using i <= size causing extra iteration
• Using Stack instead of Queue
• Not toggling direction flag

5. You want to implement zigzag level order traversal but optimize space by using a single deque (double-ended queue). Which approach correctly uses the deque to achieve zigzag traversal?

hard

A. Use deque to add nodes at front for left-to-right levels and remove from end; add nodes at end for right-to-left levels and remove from front.

B. Use deque to add nodes at the end for left-to-right levels and remove from front; add nodes at front for right-to-left levels and remove from end.

C. Use deque to add nodes only at end and remove from front for all levels.

D. Use deque to add nodes only at front and remove from end for all levels.

Solution

1. Step 1: Understand deque usage for zigzag

   For left-to-right levels, add children at the end and remove nodes from front to process in order.

2. Step 2: Reverse direction for right-to-left levels

   For right-to-left levels, add children at front and remove nodes from end to process in reverse order.

3. Final Answer:

   Use deque to add nodes at the end for left-to-right levels and remove from front; add nodes at front for right-to-left levels and remove from end. -> Option B

4. Quick Check:

   Deque add/remove ends alternate by level [OK]

Hint: Alternate deque ends for add/remove by level [OK]

Common Mistakes:

• Adding/removing from same end always
• Not reversing add/remove ends per level
• Using only queue or stack instead of deque