Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter.

Example: zig-zag level order traversal of below tree will be
0 2 1 3 4 5 6 14 13 12 11 10 9 8 7


Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?

If we think logically then we will see that we need stack in place of queue. Now again a single stack won’t serve our purpose here, we need 2 stacks: stack1 for right to left and stack2 for left to right. For identifying, whether we need to put data in stack1 or stack2, we need a flag (left2right) to indicate direction (after a level finishes).

Initially, left2right is true and we push root node in stack1 and that’s our beginning point. Now since after root node, first level fished, we toggle left2right. Until stack1 is empty, we pop values from stack1 and push values based on left2right flag. Once stack1 finishes, we toggle left2right again and switch stack’s role.

For clarification, when left2right is true, push left node first in stack and then right node. Similarly left2right is false, push right node first in stack and then left node.

Code:
void ZigZagLevelOrder(tree *root) {
stack<tree*> stack1, stack2, *cur_level, *next_level, *temp;
bool left2right = true;

cur_level = &stack1;
next_level = &stack2;

// push root in stack
cur_level->push(root);
while (!cur_level->empty()) {
tree *node = cur_level->top();
cur_level->pop();
if (node) {
cout << node->data << " ";
if (left2right) {
next_level->push(node->left);
next_level->push(node->right);
} else {
next_level->push(node->right);
next_level->push(node->left);
}
}
if (cur_level->empty()) {
left2right = !left2right;
// swap stacks
temp = Cur_level;
cur_level = next_level;
next_level = temp;
}
}
}


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.