CareerCup

do the same as breadth first traversal using Queue while keeping track of levels. While popping from Queue,whenever the level changes, toggle between directly popping from Queue and inserting the popped element into a stack. When the level changes again, empty the stack.

Use two stacks. When popping a node from stack 1, expand it from right child to left child, and the children should be pushed into stack 2; For stack 2, its the other way around. As init, A can be pushed in stack 1. Print the children when expending.

Do Breadthfirstsearch and put the values in the queue by right child first and then the left child. (Meaning adding children from right to left)

The code is similar to the one in which a line has to be inserted doing bfs. Thinking on the same lines u require an additional stack and a variable level to keep track of the level of the tree..

void printNodes (Node *temp)
{
    Queue q;
    Stack s;
    int level = 0, current_level, next_level, next_level_temp;

    if (temp != 0)
    {
        q.enqueue (temp);
        level = 1;
        current_level = 1;
        next_level = 0;
        while (!q.isEmpty ())
        {
            if (current_level == 0)
            {
                if (level % 2 == 0)         //print the even levels backwards
                {
                    for (int i = 0; i < next_level_temp; i++)
                    {
                        temp = s.pop ();
                        cout<< temp->data;
                    }
                }
                if (level % 2)           
                  next_level_temp = next_level;  //No of nodes to print in next level
                
                current_level = next_level;
                next_level = 0;
                cout<<" ";
                level++;
            }
            temp = q.dequeue ();
            if (temp->left)
            {
                q.enqueue (temp->left);
                next_level++;
            }
            if (temp->right)
            {
                q.enqueue (temp->right);
                next_level++;
            }
            if (level % 2)
                cout<<temp->data;    //print if the level is odd
            else
                s.push (temp);       //push on the stack if the level is even
            current_level--;
        }
    }
}

Using same algorithm we do for Level Order traversal using queue . here we will use an extra stack that get be filled in even case and then pop out so then we can get it printed backwards

#include<iostream>
#include<queue>
#include<stack>
using namespace std;

typedef struct nn {
    int data;
    struct nn *left;
    struct nn *right;    
}node;

node *insert(node *start, int data) {
     if(start == NULL) {
         node * p = new node;     
         p->data = data;
         p->left = NULL;
         p->right = NULL;
         start = p;     
     }
     else if(start->data > data)
         start->left = insert(start->left,data);
     else
         start->right = insert(start->right,data);
    return start;         
}

void printInOrder(node *start) {
     if(start) {
         printInOrder(start->left);
         cout << start->data << " ";
         printInOrder(start->right);      
     }
}

void printLevelOrderSpiralIterative(node *start) {
     queue<node*> levelOrder;
     stack<int> levelStack;
     levelOrder.push(start);
     levelOrder.push(NULL);
     int nullCount = 1;
     while(levelOrder.size() > 0) {
           node *start = levelOrder.front();
           levelOrder.pop();
           if(start != NULL) {
              if(nullCount % 2) cout << start->data << " ";
              else 
                 levelStack.push(start->data); 
           }
           else {
              if(levelOrder.front() != NULL) {
                 levelOrder.push(NULL);                        
                 nullCount++;
                 if(nullCount % 2) {
                      while(levelStack.size()) {
                           cout << levelStack.top()<< " ";
                           levelStack.pop();                 
                      }        
                 } 
                 cout << endl;
              }
              continue;
           }
           if(start->left) levelOrder.push(start->left); 
           if(start->right) levelOrder.push(start->right);
                
     } 
}

int main() {
    int n;
    cin >> n;
    node *start = NULL;
    while(n != -1) {
        start = insert(start,n);
        cin >> n;    
    }
    printLevelOrderSpiralIterative(start);
    system("pause");
}

You have to maintain a QUEQUE and STACK.
Starting from the ROOT node put it into QUEQUE and now delete element from the QUEQUE ,print them and put there neighbours into STACK till QUEQUE is empty. Again starting
from STACK take element from it and print them and put their neighbours into QUEQUE.
till STACK is empty.

DO it till we have both the QUEUE And STACK is empty

head = end =0;
h = height(root);
for i = 1 to h
CreateList(root, i, ((i%2)==0));

void CreateList(tree, d, front)
{
if (!tree) return;
if (d==1) {
AddToList(tree, front);
} else if (d>1) {
CreateList(root->left, d-1, front);
CreateList(root->right, d-1, front);
}
}
void AddToList(n, front) {
if (!head) head = n;
if (!end) {
end = n;
return;
}
if (front) {
n->next = head;
head = n;
} else {
end->next = n;
end = n;
}
}

head = end =0;
h = height(root);
for i = 1 to h
  CreateList(root, i, ((i%2)==0));

void CreateList(tree, d, front)
{
  if (!tree) return;
  if (d==1) {
    AddToList(tree, front);
  } else if (d>1) {
    CreateList(root->left, d-1, front);
    CreateList(root->right, d-1, front);
  }
}
void AddToList(n, front) {
  if (!head) head = n;
  if (!end) {
    end = n;
    return;
  }
  if (front) {
    n->next = head;
    head = n;
  } else {
    end->next = n;
    end = n;
  }
}

above was incorrect. correct one is:

head = 0;
h = height(root);
for i = 1 to h
  CreateList(root, i, ((i%2)==0));

void CreateList(tree, d, even)
{
 if (!tree) return;
 if (d==1) {
  AddToList(tree, front);
 } else if (d>1) {
  if (even) {
   CreateList(root->left, d-1, even);
   CreateList(root->right, d-1, even);
  } else {
   CreateList(root->right, d-1, even);
   CreateList(root->left, d-1, even);
  }
 }
}
void AddToList(n) {
  if (!head) head = nextNode = n;
  else {
   NODE* nn = new NODE(n->data); 
   nextNode->next = nn;
   nextNode = nn;
  }   
}

Please check the pseudo code and comment
while(nxtelement)
if(level==even)
{
if(first_instance)
{
push all elements from stack to Q;//using stackpointer
stackpointer=quepointer+1;
}
push in stack;//left & right
}
push in queue;//left & right

nxtelement=Deque;
}

import java.util.Stack;

public class ZigZagTraversal {

	class BinaryTree {
		public Character value;
		public BinaryTree left = null, right = null;

		public BinaryTree(Character value) {
			this.value = value;
		}

	}

	public void doZigZagTraversal(BinaryTree root) {
		if (root == null)
			return;
		Boolean pushInReverseOrder = false;
		Stack<BinaryTree> currentLevelVisitStore = new Stack<>();
		Stack<BinaryTree> nextLevelVisitStore = new Stack<>();
		currentLevelVisitStore.push(root);
		while (!currentLevelVisitStore.isEmpty()) {
			BinaryTree node = currentLevelVisitStore.pop();
			if (node != null) {
				System.out.print(node.value + " ");
				if (pushInReverseOrder) {
					if (node.right != null)
						nextLevelVisitStore.push(node.right);
					if (node.left != null)
						nextLevelVisitStore.push(node.left);
				} else {
					if (node.left != null)
						nextLevelVisitStore.push(node.left);
					if (node.right != null)
						nextLevelVisitStore.push(node.right);
				}
			}
			if (currentLevelVisitStore.isEmpty()) {
				Stack<BinaryTree> levelChangeSwapPointer = currentLevelVisitStore;
				currentLevelVisitStore = nextLevelVisitStore;
				nextLevelVisitStore = levelChangeSwapPointer;
				pushInReverseOrder = !pushInReverseOrder;
				System.out.print(" "); // just to highlight the change in order of printing. 
			}
		}
	}

	public static void main(String args[]) {
		ZigZagTraversal zzt = new ZigZagTraversal();
		BinaryTree bt = zzt.new BinaryTree('A');

		bt.left = zzt.new BinaryTree('B');
		bt.right = zzt.new BinaryTree('C');

		bt.left.left = zzt.new BinaryTree('D');
		bt.left.right = zzt.new BinaryTree('E');

		bt.right.left = zzt.new BinaryTree('F');
		bt.right.right = zzt.new BinaryTree('G');

		bt.left.left.left = zzt.new BinaryTree('H');
		bt.left.left.right = zzt.new BinaryTree('I');

		bt.left.right.left = zzt.new BinaryTree('J');

		zzt.doZigZagTraversal(bt);
	}

}