Zigzag Traversal of a Binary Tree - Iterative - Visualization

Understanding the Problem

Zigzag traversal of a binary tree means traversing its nodes level by level, but alternating the direction of traversal at each level. At the first level, we go from left to right. At the second level, we go from right to left. Then left to right again, and so on. This pattern continues until all levels are visited.

To perform this traversal, we need to keep track of the current level, the direction of traversal, and the child nodes to visit next. A queue or stack can help us manage the order of processing, depending on the traversal direction.

Step-by-Step Solution with Example

Step 1: Understand the structure of the tree

Let’s consider the following binary tree as an example:

        1
      /        2     3
    /    /    4   5 6   7

The expected zigzag traversal output for this tree is: [1, 3, 2, 4, 5, 6, 7]

Step 2: Initialize data structures

We use two stacks:

• currentLevel - holds nodes for the current level being processed
• nextLevel - collects nodes for the next level

Step 3: Push the root node into currentLevel stack

Start with the root node 1 in currentLevel stack. Set leftToRight to true since the first level should go left to right.

Step 4: Traverse the current level

While currentLevel is not empty:

• Pop a node from currentLevel
• Add its value to the result list
• If leftToRight is true, push left child first, then right child to nextLevel
• If false, push right child first, then left child

Step 5: Move to next level

When currentLevel is empty:

• Swap currentLevel and nextLevel
• Toggle leftToRight

Step 6: Final Output

After all levels are visited, the collected result is the zigzag level order traversal of the binary tree.

For our example, this results in: [1, 3, 2, 4, 5, 6, 7]

Edge Cases

Case 1: Empty Tree

If the root is null, there are no nodes to traverse. The output should be an empty list: []

Case 2: Single Node Tree

If there is only one node in the tree, the traversal result is simply that node: [root]. No direction change is needed.

Case 3: Left-Skewed Tree

Each node has only a left child. Since each level has only one node, the direction change doesn’t affect the result. The output is top-to-bottom: [root, left1, left2, ...]

Case 4: Right-Skewed Tree

Each node has only a right child. Like the left-skewed case, the output is top-to-bottom: [root, right1, right2, ...]

Case 5: Uneven Tree

In trees where one subtree is deeper than the other, the algorithm still works. The key is managing the push order depending on the direction flag, ensuring every level is handled correctly regardless of shape.

Finally

Zigzag traversal is a simple variation of level order traversal, made possible by using two stacks and a direction flag. By working level by level and flipping the order of child insertion, we can achieve the desired zigzag pattern.

This approach is intuitive and works for all kinds of trees — complete, skewed, or even empty — as long as we check base conditions and handle edge cases properly.

1. If the binary tree is empty, return an empty result.
2. Initialize two stacks: currentStack and nextStack. Push the root node onto currentStack.
3. Set a boolean flag leftToRight to true to indicate the traversal direction.
4. While currentStack is not empty, do the following:
1. Initialize an empty list to store the values of the current level.
2. While currentStack is not empty, pop a node from it and record its value.
3. If leftToRight is true, push the node's left child then right child (if they exist) onto nextStack; otherwise, push the node's right child then left child onto nextStack.
4. After processing the current level, add the recorded values to the result.
5. Swap currentStack with nextStack and toggle the leftToRight flag.
5. Continue until all levels have been processed; the collected values form the zigzag traversal of the binary tree.