Zig Zag Traversal of a tree...

Q : Given a binary tree.. Print the elements from the 1st row to the last row (each row corresponding to one set of siblings in the tree) such that

For every odd row : print the elements from left to right
For every even row : print the elements from right to left.

Answer :


Use two stacks. One stack to store the even row pointers and another to store the odd row pointers
Let root be the root element of the tree - lets say the row is even - 0

stack1 - contains the even pointers
stack2 - contains the odd pointers

flag = true;
while( flag !=false)
{
push root into stack1
while( ( s1_current = pop(stack1)) ! = null )
{
print(s1_current->element);
push(s1_current->left) into stack2; //if the element is not null
push(s1_current->right) into stack2; //if the element is not null
}
while( (s2_current = pop(stack2)) != null)
{
print(s2_current->element);
push(s2_current -> right) into stack1; // if the element is not null
push(s2_current -> left) into stack1; // if the element is not null
}
if(top(stack1) != null) // basically to check if stack1 is empty
{
flag = true;
}

}

Time Complexity : O(n)

Space Complexity : The worst case space complexity for this problem would be 2 ^ log(n) since log(n) corresponds to the height of the tree.