Zigzag Level Order Traversal in DSA C#

Mental Model

We visit tree nodes level by level, but alternate the direction of visiting nodes at each level.

Analogy: Imagine reading lines of text where you read the first line left to right, the second line right to left, then left to right again, like a zigzag pattern.

      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)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3 -> 4, 5, null, 6

Goal: Traverse the tree level by level, alternating direction each level, collecting node values.

Step 1: Start at root level (level 0), direction left to right

Level 0: [1] -> null

Why: We begin traversal from the root node, reading left to right.

Step 2: Collect nodes at level 0: [1]

Result so far: [[1]]

Why: First level collected in normal order.

Step 3: Move to level 1, direction right to left

Level 1: [3 -> 2] -> null

Why: Next level is traversed in reverse order.

Step 4: Collect nodes at level 1 in reverse: [3, 2]

Result so far: [[1], [3, 2]]

Why: We reverse the order of nodes at this level.

Step 5: Move to level 2, direction left to right

Level 2: [4 -> 5 -> 6] -> null

Why: Direction switches back to left to right.

Step 6: Collect nodes at level 2: [4, 5, 6]

Result so far: [[1], [3, 2], [4, 5, 6]]

Why: Final level collected in normal order.

Result:

Final zigzag traversal: [[1], [3, 2], [4, 5, 6]]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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

public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        if (root == null) return result;

        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        bool leftToRight = true;

        while (queue.Count > 0) {
            int levelSize = queue.Count;
            var levelNodes = new int[levelSize];

            for (int i = 0; i < levelSize; i++) {
                var node = queue.Dequeue();
                int index = leftToRight ? i : (levelSize - 1 - i);
                levelNodes[index] = node.val;

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

            result.Add(levelNodes);
            leftToRight = !leftToRight;
        }

        return result;
    }

    public static void Main() {
        var root = new TreeNode(1,
            new TreeNode(2,
                new TreeNode(4),
                new TreeNode(5)),
            new TreeNode(3,
                null,
                new TreeNode(6)));

        var sol = new Solution();
        var res = sol.ZigzagLevelOrder(root);

        foreach (var level in res) {
            Console.WriteLine(string.Join(", ", level));
        }
    }
}

queue.Enqueue(root);

Start traversal from root node.

while (queue.Count > 0) {

Process nodes level by level until none left.

int levelSize = queue.Count;

Determine number of nodes at current level.

int index = leftToRight ? i : (levelSize - 1 - i);

Calculate index to insert node value based on current direction.

if (node.left != null) queue.Enqueue(node.left);

Add left child to queue for next level.

if (node.right != null) queue.Enqueue(node.right);

Add right child to queue for next level.

leftToRight = !leftToRight;

Switch direction for next level.

Output

1

3, 2

4, 5, 6

Complexity Analysis

Time: O(n) because each node is visited exactly once during traversal.

Space: O(n) because the queue and result list store all nodes at worst case.

vs Alternative: Compared to normal level order traversal, this adds only a direction toggle and index calculation, keeping the same O(n) time and space.

Edge Cases

Empty tree (root is null)

Returns empty list immediately without processing.

DSA C#

if (root == null) return result;

Tree with single node

Returns list with one level containing that node.

DSA C#

queue.Enqueue(root);

Tree with only left or only right children

Traverses levels normally, direction toggles still apply.

DSA C#

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

When to Use This Pattern

When a problem asks for level order traversal but with alternating directions each level, use the zigzag level order traversal pattern to handle direction switching efficiently.

Common Mistakes

Mistake: Not toggling the direction flag after each level, causing all levels to be traversed in the same order.
Fix: Toggle the direction boolean at the end of each level processing: leftToRight = !leftToRight;

Mistake: Inserting node values in the wrong order without adjusting index, resulting in incorrect zigzag output.
Fix: Calculate the insertion index based on direction: index = leftToRight ? i : (levelSize - 1 - i);

Summary

Traverses a binary tree level by level, alternating the order of nodes at each level.

Use when you need to collect nodes in a zigzag or snake-like pattern across levels.

The key is toggling direction and inserting node values in reverse order on alternate levels.

Practice

1. What does the Zigzag Level Order Traversal of a binary tree do differently compared to a normal level order traversal?

easy

A. It alternates the direction of traversal at each level, left to right then right to left.

B. It visits nodes only on the left subtree.

C. It visits nodes in reverse order of their insertion.

D. It traverses 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: Identify zigzag difference

   Zigzag traversal alternates direction each level: first left to right, then right to left, and so on.

3. Final Answer:

   It alternates the direction of traversal at each level, left to right then right to left. -> Option A

4. Quick Check:

   Zigzag = alternate directions [OK]

Hint: Remember zigzag means direction flips every level [OK]

Common Mistakes:

• Thinking it only visits left subtree
• Assuming traversal is always left to right
• Confusing zigzag with reverse order

2. Which of the following C# code snippets correctly initializes a queue to perform a zigzag level order traversal?

easy

A. List<TreeNode> queue = new List<TreeNode>();

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

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

D. Dictionary queue = new Dictionary();

Solution

1. Step 1: Identify data structure for BFS

   Queue is used for breadth-first search to process nodes level by level.

2. Step 2: Check code snippet correctness

   Queue<TreeNode> queue = new Queue<TreeNode>(); correctly declares a Queue of TreeNode objects, suitable for traversal.

3. Final Answer:

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

4. Quick Check:

   Queue for BFS = Queue<TreeNode> queue = new Queue<TreeNode>(); [OK]

Hint: Use Queue for level order traversal in C# [OK]

Common Mistakes:

• Using Stack instead of Queue for BFS
• Using List which lacks FIFO behavior
• Using Dictionary which is not suitable here

3. Given the binary tree:

    1
   / \
  2   3
 / \   \
4   5   6

What is the output of zigzag level order traversal?

medium

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

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

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 = [[1], [3, 2], [4, 5, 6]] [OK]

Hint: Alternate direction each level, reverse nodes on odd levels [OK]

Common Mistakes:

• Not reversing nodes on alternate levels
• Mixing node order in last level
• Confusing left and right child order

4. Consider this C# code snippet for zigzag traversal:

if (level % 2 == 0)
    result.Add(currentLevel);
else
    result.Add(currentLevel.Reverse().ToList());

What is the bug in this code?

medium

A. It reverses the list on even levels instead of odd levels.

B. It reverses the list on odd levels instead of even levels.

C. It reverses the original list causing side effects.

D. It does not reverse the list at all.

Solution

1. Step 1: Understand zigzag pattern

   Zigzag reverses nodes on odd levels (1, 3, 5...), not even levels (0, 2, 4...).

2. Step 2: Analyze code condition

   The condition correctly identifies even/odd levels for reversal.

3. Step 3: Identify the actual issue

   currentLevel.Reverse() (List<TreeNode>.Reverse) modifies the list in place and returns void, causing side effects and a compilation error on .ToList().

4. Final Answer:

   It reverses the original list causing side effects. -> Option C

5. Quick Check:

   List.Reverse() in-place modifies original [OK]

Hint: Reverse nodes only on odd levels (1, 3, 5...) [OK]

Common Mistakes:

• Reversing on even levels instead of odd
• Modifying original list causing bugs
• Not reversing at all

5. You want to perform zigzag level order traversal on a binary tree but only collect nodes with even values. Which modification is best to apply?

hard

A. Use a stack instead of a queue to collect only even nodes.

B. Reverse the entire result list after traversal to get even nodes first.

C. Skip reversing on odd levels to keep order consistent for even nodes.

D. Filter nodes by even value before adding them to the current level list during traversal.

Solution

1. Step 1: Identify filtering requirement

   We want only even-valued nodes in the output, so filter nodes during traversal.

2. Step 2: Apply filtering during level collection

   Filter nodes by checking if value is even before adding to current level list.

3. Step 3: Keep zigzag logic intact

   After filtering, apply zigzag reversal as usual on filtered nodes.

4. Final Answer:

   Filter nodes by even value before adding them to the current level list during traversal. -> Option D

5. Quick Check:

   Filter during traversal = Filter nodes by even value before adding them to the current level list during traversal. [OK]

Hint: Filter nodes while collecting each level, then zigzag [OK]

Common Mistakes:

• Reversing entire result instead of filtering
• Skipping reversal breaks zigzag pattern
• Using stack incorrectly for filtering