Zig Zag Binary Tree Traversal In Reverse Order

package tree;

public class Node{
 
 private Node left;
 private Node right;
 private int data;
 
 public Node(int data){
  this.data=data;
 }

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }
}

package tree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*    

              50
              /\  
          40      60
          /\      /\
        30  45   55 70
        /\
       20 35
  
  Level Order         : 50, 40, 60, 30, 45, 55, 70, 20, 35
  Reverse Level Order : 20, 35, 30, 45, 55, 70, 40, 60, 50

*/

public class ZigZagTreeTraversalInReverseOrder {
 private Node rootNode;

 public static void main(String[] args) {
  new ZigZagTreeTraversalInReverseOrder();
 }

 public ZigZagTreeTraversalInReverseOrder(){

  addNode(rootNode, 20); 
  addNode(rootNode, 8); 
  addNode(rootNode, 22); 
  addNode(rootNode, 4); 
  addNode(rootNode, 12); 
  addNode(rootNode, 1); 
  addNode(rootNode, 2);
  addNode(rootNode, 10);
  addNode(rootNode, 14);
  
  zigZagTraverse(rootNode);  
 }

 private void zigZagTraverse(Node rootNode) {
  Queue<Node> q = new LinkedList<Node>();
  Stack<Node> s= new Stack<Node>();
  
  if(rootNode==null)
   return;
  
  q.add(rootNode);
  while(!q.isEmpty()){
   Node temp = q.poll();
   if(temp.getRight()!=null)
    q.add(temp.getRight());
   
   if(temp.getLeft()!=null)
    q.add(temp.getLeft());
   
   s.push(temp);
  }
  
  while(!s.isEmpty())
   System.out.print((s.pop()).getData() + " ");
 }
  

 private void addNode(Node rootNode, int data){

  //First check is there any Nodes present.
  if(rootNode==null){
   // No Nodes are Present, create one and assign it to startNode
   Node temp1=new Node(data);
   this.rootNode=temp1;
  }else{
   //Nodes present, So check the proper position where to add New Node.

   //Checking whether Left child and Right child are present for root Node. 
   if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
    //Left and Right Child exist, Also, we need to add ne Node in Sequential Fashion of Left and Right, 
    //We have to scan all Levels one by one to check a proper place for new Node.
    //Also, we for each and every node we need to check whether Left and Right Exist, 
    //So we need to store them for later Processing that is why we introduced Queue.

    Queue<Node> queue = new LinkedList<Node>();
    queue.add(rootNode);

    while(!queue.isEmpty()){
     Node obj = (Node)queue.poll();
     if(obj.getLeft()!=null && obj.getRight()!=null){
      queue.add(obj.getLeft());
      queue.add(obj.getRight());
     }else if(obj.getLeft()==null){
      Node temp1=new Node(data);
      obj.setLeft(temp1);
      break;
     }else{
      Node temp1=new Node(data);
      obj.setRight(temp1);
      break;
     }
    }

   }else{
    // We reach this condition when either Left or Right is Null, but not sure which side is Null.
    if(rootNode.getLeft()==null){
     Node temp1=new Node(data);
     rootNode.setLeft(temp1);
    }else{
     Node temp1=new Node(data);
     rootNode.setRight(temp1);
    }
   }
  }
 }
}