Binary Tree Zigzag Level Order Traversal

Problem:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level's order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node's value. Whenever the current level's order is from left->right, you push the node's left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level's order is from right->left, you would push the node's right child first, then its left child. Finally, don't forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

void printLevelOrderZigZag(BinaryTree *root) {
    stack<BinaryTree*> currentLevel, nextLevel;
    bool leftToRight = true;
    currentLevel.push(root);
    while (!currentLevel.empty()) {
        BinaryTree *currNode = currentLevel.top();
        currentLevel.pop();
        if (currNode) {
            cout << currNode->data << " ";
            if (leftToRight) {
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            } else {
                nextLevel.push(currNode->right);
                nextLevel.push(currNode->left);
            }
        }
        if (currentLevel.empty()) {
            cout << endl;
            leftToRight = !leftToRight;
            swap(currentLevel, nextLevel);
        }
    }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://discuss.leetcode.com/questions/52/binary-tree-zigzag-level-order-traversal