Zigzag Level Order Traversal in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue for BFS traversal.

DSA Java

Queue<TreeNode> queue = new [1]<>();

Drag options to blanks, or click blank then click option'

AHashSet

BStack

CArrayList

DLinkedList

Attempts:

3 left

💡 Hint

Common Mistakes

Using Stack instead of a queue.

Using ArrayList which does not implement Queue interface.

We use LinkedList to implement the queue for BFS traversal in Java.

2fill in blank

medium

Complete the code to add the root node to the queue.

DSA Java

if (root != null) queue.[1](root);

Drag options to blanks, or click blank then click option'

Aoffer

BaddFirst

Cpush

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using push() which is for stacks.

Using addFirst() which is for Deque.

The offer() method adds an element to the queue safely.

3fill in blank

hard

Fix the error in the code to remove the current node from the queue.

DSA Java

TreeNode node = queue.[1]();

Drag options to blanks, or click blank then click option'

Apoll

Bpop

CremoveLast

Dpeek

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() which is for stacks.

Using peek() which does not remove the element.

poll() removes and returns the head of the queue or returns null if empty.

4fill in blank

hard

Fill both blanks to add child nodes to the queue if they exist.

DSA Java

if (node.[1] != null) queue.[2](node.left);
if (node.right != null) queue.offer(node.right);

Drag options to blanks, or click blank then click option'

Aleft

Bright

Coffer

Dpoll

Attempts:

3 left

💡 Hint

Common Mistakes

Checking node.right instead of node.left in the first if.

Using poll() instead of offer() to add elements.

We check node.left and add it to the queue using offer().

5fill in blank

hard

Fill all three blanks to reverse the level list when needed and add it to the result.

DSA Java

if (leftToRight) {
    result.add(new ArrayList<>(levelList));
} else {
    Collections.[1](levelList);
    result.[2](new ArrayList<>(levelList));
}
leftToRight = ![3];

Drag options to blanks, or click blank then click option'

Areverse

Badd

CleftToRight

Dclear

Attempts:

3 left

💡 Hint

Common Mistakes

Using clear() instead of reverse().

Forgetting to toggle leftToRight.

We reverse levelList, add it to result, and toggle leftToRight boolean.

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