Zigzag Level Order Traversal in DSA C# - Build from Scratch

Zigzag Level Order Traversal

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to list the family members level by level, but with a twist: the first level is listed left to right, the second level right to left, the third level left to right again, and so on, zigzagging through the tree.

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

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a variable to track the current level direction (left to right or right to left)

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

Print the traversal result as a list of lists showing each level's values in zigzag order

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in scenarios like printing organizational charts, family trees, or any hierarchical data where alternating order display improves readability.

💼 Career

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

1

Create the binary tree structure

Create a class called TreeNode with an int val, and two TreeNode references called left and right. Then create the exact binary tree below by creating TreeNode instances and linking them:

Root node value: 1
Left child of root: 2
Right child of root: 3
Left child of node 2: 4
Right child of node 2: 5
Left child of node 3: 6
Right child of node 3: 7
Store the root node in a variable called root.

DSA C#

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

Hint

Define the TreeNode class first, then create the nodes from bottom to top linking children to parents.

2

Add a direction flag for zigzag traversal

Create a boolean variable called leftToRight and set it to true. This will track the direction of traversal for each level.

DSA C#

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;
    }
}

TreeNode root = new TreeNode(1,
    new TreeNode(2,
        new TreeNode(4),
        new TreeNode(5)),
    new TreeNode(3,
        new TreeNode(6),
        new TreeNode(7))
);

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

Hint

This flag will help us decide if we add nodes left to right or right to left at each level.

3

Implement zigzag level order traversal

Write code to perform zigzag level order traversal on the binary tree starting from root. Use a Queue<TreeNode> called queue to hold nodes for each level. Use a List<List<int>> called result to store values level by level. For each level, create a List<int> called levelNodes. If leftToRight is true, add node values to levelNodes in order; if false, add them in reverse order. After processing each level, toggle leftToRight. Store the final traversal in result.

DSA C#

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;
    }
}

TreeNode root = new TreeNode(1,
    new TreeNode(2,
        new TreeNode(4),
        new TreeNode(5)),
    new TreeNode(3,
        new TreeNode(6),
        new TreeNode(7))
);

bool leftToRight = true;

// Implement zigzag level order traversal and store result in List> result
// Your code here

Hint

Use a queue to process nodes level by level. Use Insert(0, value) to add values at the front when direction is right to left.

4

Print the zigzag traversal result

Print the result list of lists so that each level's values are shown as a list on a new line. Use a foreach loop to iterate over result and print each inner list as comma-separated values enclosed in square brackets.

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;
    }
}

TreeNode root = new TreeNode(1,
    new TreeNode(2,
        new TreeNode(4),
        new TreeNode(5)),
    new TreeNode(3,
        new TreeNode(6),
        new TreeNode(7))
);

bool leftToRight = true;

Queue queue = new Queue();
queue.Enqueue(root);
List> result = new List>();

while (queue.Count > 0)
{
    int levelSize = queue.Count;
    List levelNodes = new List();
    for (int i = 0; i < levelSize; i++)
    {
        TreeNode node = queue.Dequeue();
        if (leftToRight)
            levelNodes.Add(node.val);
        else
            levelNodes.Insert(0, node.val);

        if (node.left != null) queue.Enqueue(node.left);
        if (node.right != null) queue.Enqueue(node.right);
    }
    result.Add(levelNodes);
    leftToRight = !leftToRight;
}

// Print the zigzag traversal result
// Your code here

Hint

Use string.Join to join the integers with commas and print each level on a new line enclosed in square brackets.

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