Zigzag Traversal of a Binary Tree

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.

Zigzag Traversal of a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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