Zigzag Traversal of a Binary Tree - Iterative Approach

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