Zigzag Traversal of a Binary Tree - Iterative Approach

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a binary tree, perform a zigzag (also called spiral order) traversal using an iterative approach. In zigzag traversal, the nodes of the binary tree are printed level by level, but the direction alternates — the first level is printed left to right, the second level right to left, the third left to right again, and so on. The task is to return a list of values representing this traversal order.

Examples❯

Input Tree Zigzag Traversal Output Description
[1, 2, 3, 4, 5, null, 6]
[[1], [3, 2], [4, 5, 6]] Standard tree with three levels, showcasing left-to-right and right-to-left alternation
[1]
[[1]] Edge case: Single-node tree (root only)
[] [] Edge case: Empty tree with no nodes
[1, 2, null, 3, null, null, null, 4]
[[1], [2], [3], [4]] Left-skewed tree; no right branches, still follows zigzag pattern per level
[1, null, 2, null, null, null, 3]
[[1], [2], [3]] Right-skewed tree; no left branches, still alternates direction at each level
[7, 9, 8, 1, 5, 3, 6]
[[7], [8, 9], [1, 5, 3, 6]] Balanced tree with full left and right subtrees to demonstrate alternating level order

Solution❯

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
We also use a boolean flag leftToRight to track direction of traversal.

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
Repeat until all nodes are processed.

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.

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void zigzagTraversal(TreeNode* root) {
    if (!root) return;
    TreeNode* currentStack[100];
    TreeNode* nextStack[100];
    int top1 = -1, top2 = -1;
    int leftToRight = 1;
    currentStack[++top1] = root;

    while (top1 >= 0) {
        while (top1 >= 0) {
            TreeNode* node = currentStack[top1--];
            printf("%d ", node->val);
            if (leftToRight) {
                if (node->left) nextStack[++top2] = node->left;
                if (node->right) nextStack[++top2] = node->right;
            } else {
                if (node->right) nextStack[++top2] = node->right;
                if (node->left) nextStack[++top2] = node->left;
            }
        }
        printf("\n");
        TreeNode** temp = currentStack;
        memcpy(currentStack, nextStack, sizeof(nextStack));
        top1 = top2;
        top2 = -1;
        leftToRight = !leftToRight;
    }
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    zigzagTraversal(root);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...