Zigzag Level Order Traversal in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Level Order Traversal on a simple tree

What is the output of the zigzag level order traversal for the given binary tree?

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// Tree structure:
//      1
//     / \
//    2   3
//   /     \
//  4       5

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 node = queue.poll();
            if (leftToRight) {
                level.addLast(node.val);
            } else {
                level.addFirst(node.val);
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

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

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

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

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

💡 Hint

Remember that the traversal direction alternates at each level.

The traversal starts left to right at level 1: [1].

At level 2, it goes right to left: [3, 2].

At level 3, it goes left to right again: [4, 5].

❓ Predict Output

intermediate

Zigzag traversal output with single node tree

What is the output of the zigzag level order traversal for a tree with only one node (value 10)?

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// Tree structure:
// 10

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 node = queue.poll();
            if (leftToRight) {
                level.addLast(node.val);
            } else {
                level.addFirst(node.val);
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

A []

B [[10]]

C [[10, 10]]

D [[]]

💡 Hint

A single node tree has only one level.

With only one node, the traversal returns a list with one list containing that node's value.

🔧 Debug

advanced

Identify the error in zigzag traversal code

What error will the following code produce when run on a non-empty tree?

DSA Java

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();
        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.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

A Throws IndexOutOfBoundsException when adding at index 0 in ArrayList

B NullPointerException when root is null

C No error; code runs correctly and returns zigzag traversal

D Infinite loop due to queue never emptying

💡 Hint

ArrayList supports adding at index 0, but it is less efficient than LinkedList.

The code uses ArrayList and inserts at index 0 when traversing right to left. This works correctly but is less efficient.

No exceptions occur for normal input.

🧠 Conceptual

advanced

Data structure choice for efficient zigzag traversal

Which data structure is best to efficiently support adding elements at both ends during zigzag level order traversal?

A LinkedList

B ArrayList

C HashSet

D Stack

💡 Hint

Think about adding elements at the front and back efficiently.

LinkedList allows efficient insertion at both ends (front and back) which is needed for zigzag traversal.

ArrayList is inefficient for front insertions.

HashSet and Stack do not support ordered insertion at both ends.

🚀 Application

expert

Number of levels in zigzag traversal output

Given a complete binary tree with 7 nodes, how many lists will the zigzag level order traversal output contain?

A 2

B 4

C 7

D 3

💡 Hint

Count the height of a complete binary tree with 7 nodes.

A complete binary tree with 7 nodes has height 3 (levels 1, 2, and 3).

Each level corresponds to one list in the output.

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