ProgramGuru

Zigzag Traversal of a Binary Tree

Problem and examples

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.
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

Explore Zigzag Traversal of a Binary Tree - Iterative

Load an example or enter your own input. Use the player controls to follow each change.

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.

  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.

Implementation and efficiency

C implementation

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

C++ implementation

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<vector<int>> zigzagTraversal(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    stack<TreeNode*> currentStack, nextStack;
    currentStack.push(root);
    bool leftToRight = true;
    vector<int> level;

    while (!currentStack.empty()) {
        TreeNode* node = currentStack.top();
        currentStack.pop();
        level.push_back(node->val);

        if (leftToRight) {
            if (node->left) nextStack.push(node->left);
            if (node->right) nextStack.push(node->right);
        } else {
            if (node->right) nextStack.push(node->right);
            if (node->left) nextStack.push(node->left);
        }

        if (currentStack.empty()) {
            result.push_back(level);
            level.clear();
            swap(currentStack, nextStack);
            leftToRight = !leftToRight;
        }
    }

    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    vector<vector<int>> res = zigzagTraversal(root);
    for (auto& level : res) {
        for (int val : level) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagTraversal(root):
    if not root:
        return []
    result = []
    currentStack = [root]
    nextStack = []
    leftToRight = True
    level = []
    while currentStack:
        node = currentStack.pop()
        level.append(node.val)
        if leftToRight:
            if node.left:
                nextStack.append(node.left)
            if node.right:
                nextStack.append(node.right)
        else:
            if node.right:
                nextStack.append(node.right)
            if node.left:
                nextStack.append(node.left)
        if not currentStack:
            result.append(level)
            level = []
            currentStack, nextStack = nextStack, []
            leftToRight = not leftToRight
    return result

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(zigzagTraversal(root))

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class ZigzagTraversal {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> currentStack = new Stack<>();
        Stack<TreeNode> nextStack = new Stack<>();
        currentStack.push(root);
        boolean leftToRight = true;
        List<Integer> levelList = new ArrayList<>();

        while (!currentStack.isEmpty()) {
            TreeNode node = currentStack.pop();
            levelList.add(node.val);
            if (leftToRight) {
                if (node.left != null) nextStack.push(node.left);
                if (node.right != null) nextStack.push(node.right);
            } else {
                if (node.right != null) nextStack.push(node.right);
                if (node.left != null) nextStack.push(node.left);
            }
            if (currentStack.isEmpty()) {
                result.add(new ArrayList<>(levelList));
                levelList.clear();
                Stack<TreeNode> temp = currentStack;
                currentStack = nextStack;
                nextStack = temp;
                leftToRight = !leftToRight;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        ZigzagTraversal sol = new ZigzagTraversal();
        System.out.println(sol.zigzagLevelOrder(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function zigzagTraversal(root) {
    if (!root) return [];
    const result = [];
    let currentStack = [root];
    let nextStack = [];
    let leftToRight = true;
    let level = [];
    while (currentStack.length) {
        const node = currentStack.pop();
        level.push(node.val);
        if (leftToRight) {
            if (node.left) nextStack.push(node.left);
            if (node.right) nextStack.push(node.right);
        } else {
            if (node.right) nextStack.push(node.right);
            if (node.left) nextStack.push(node.left);
        }
        if (currentStack.length === 0) {
            result.push(level);
            level = [];
            [currentStack, nextStack] = [nextStack, []];
            leftToRight = !leftToRight;
        }
    }
    return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(zigzagTraversal(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func zigzagTraversal(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var result [][]int
    currentStack := []*TreeNode{root}
    nextStack := []*TreeNode{}
    leftToRight := true
    var level []int

    for len(currentStack) > 0 {
        node := currentStack[len(currentStack)-1]
        currentStack = currentStack[:len(currentStack)-1]
        level = append(level, node.Val)
        if leftToRight {
            if node.Left != nil {
                nextStack = append(nextStack, node.Left)
            }
            if node.Right != nil {
                nextStack = append(nextStack, node.Right)
            }
        } else {
            if node.Right != nil {
                nextStack = append(nextStack, node.Right)
            }
            if node.Left != nil {
                nextStack = append(nextStack, node.Left)
            }
        }
        if len(currentStack) == 0 {
            result = append(result, level)
            level = []int{}
            currentStack, nextStack = nextStack, []*TreeNode{}
            leftToRight = !leftToRight
        }
    }
    return result
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}
    res := zigzagTraversal(root)
    for _, level := range res {
        fmt.Println(level)
    }
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().left = Some(TreeNode::new(2));
    root.borrow_mut().right = Some(TreeNode::new(3));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(4));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(5));
    println!("Zigzag traversal not implemented fully, just tree built");
}

Kotlin implementation

class TreeNode(val `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun zigzagTraversal(root: TreeNode?): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    if (root == null) return result
    var currentStack = mutableListOf(root)
    var nextStack = mutableListOf<TreeNode>()
    var leftToRight = true
    var level = mutableListOf<Int>()

    while (currentStack.isNotEmpty()) {
        val node = currentStack.removeAt(currentStack.size - 1)
        level.add(node.`val`)
        if (leftToRight) {
            node.left?.let { nextStack.add(it) }
            node.right?.let { nextStack.add(it) }
        } else {
            node.right?.let { nextStack.add(it) }
            node.left?.let { nextStack.add(it) }
        }
        if (currentStack.isEmpty()) {
            result.add(level)
            level = mutableListOf()
            currentStack = nextStack
            nextStack = mutableListOf()
            leftToRight = !leftToRight
        }
    }
    return result
}

fun main() {
    val root = TreeNode(1).apply {
        left = TreeNode(2).apply {
            left = TreeNode(4)
            right = TreeNode(5)
        }
        right = TreeNode(3)
    }
    println(zigzagTraversal(root))
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function zigzagTraversal(root: TreeNode | null): number[][] {
    if (!root) return [];
    const result: number[][] = [];
    let currentStack: TreeNode[] = [root];
    let nextStack: TreeNode[] = [];
    let leftToRight = true;
    let level: number[] = [];

    while (currentStack.length > 0) {
        const node = currentStack.pop()!;
        level.push(node.val);
        if (leftToRight) {
            if (node.left) nextStack.push(node.left);
            if (node.right) nextStack.push(node.right);
        } else {
            if (node.right) nextStack.push(node.right);
            if (node.left) nextStack.push(node.left);
        }

        if (currentStack.length === 0) {
            result.push(level);
            level = [];
            [currentStack, nextStack] = [nextStack, []];
            leftToRight = !leftToRight;
        }
    }
    return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(zigzagTraversal(root));