Zigzag Traversal of a Binary Tree - Iterative Approach

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

Visualization Player

Solution❯

Case 1: Empty Tree

If the binary tree is empty (i.e., root is null), then there's nothing to traverse. So, the expected output is simply an empty list. This is the base case and should be handled first in your solution logic to avoid errors.

Case 2: Single Node Tree

If the tree contains only a root node and no children, the zigzag traversal is just the root itself. This is straightforward since there’s only one level and hence no alternating direction needed.

Case 3: Full Tree with Multiple Levels

This is the most common scenario where the tree has multiple levels and child nodes. The traversal begins at the root level (left to right), then flips direction for the next level (right to left), and so on. To implement this iteratively, two stacks are used: one for the current level and one for the next. Depending on the direction, we push children in different orders — left then right if going left-to-right, or right then left if going right-to-left.

Case 4: Left-Skewed Tree

In a left-skewed tree, each node has only a left child. Although we still alternate direction, each level contains only one node, so the order of printing doesn’t change. The result is simply the nodes from top to bottom.

Case 5: Right-Skewed Tree

Similarly, in a right-skewed tree where each node has only a right child, the zigzag traversal becomes identical to a top-to-bottom traversal since each level contains just one node. Direction toggling has no visible impact here as well.

By using two stacks and carefully managing the traversal direction, this iterative solution efficiently captures the zigzag pattern and works for all types of binary trees — balanced, skewed, or even empty.

Algorithm Steps❯

If the binary tree is empty, return an empty result.
Initialize two stacks: currentStack and nextStack. Push the root node onto currentStack.
Set a boolean flag leftToRight to true to indicate the traversal direction.
While currentStack is not empty, do the following:

Initialize an empty list to store the values of the current level.
While currentStack is not empty, pop a node from it and record its value.
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.
After processing the current level, add the recorded values to the result.
Swap currentStack with nextStack and toggle the leftToRight flag.

Continue until all levels have been processed; the collected values form the zigzag traversal of the binary tree.

Code

Python

Java

JavaScript

C++

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

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      / \   
    #     4   5  
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(zigzagTraversal(root))

⬅ Previous TopicBottom View of a Binary Tree

Next Topic ⮕Check if a Binary Tree is Balanced

Comments

Loading comments...