Here’s the code:
import java.util.*;
public class Main {
static Scanner scn = new Scanner(System.in);
public static void main(String[] args) {
Main m = new Main();
BinaryTree bt = m.new BinaryTree();
bt.levelOrderZZ();
}
private class BinaryTree {
private class Node {
int data;
Node left;
Node right;
}
private Node root;
private int size;
public BinaryTree() {
this.root = this.takeInput(null, false);
}
public Node takeInput(Node parent, boolean ilc) {
int cdata = scn.nextInt();
Node child = new Node();
child.data = cdata;
this.size++;
// left
boolean hlc = scn.nextBoolean();
if (hlc) {
child.left = this.takeInput(child, true);
}
// right
boolean hrc = scn.nextBoolean();
if (hrc) {
child.right = this.takeInput(child, false);
}
// return
return child;
}
public void levelOrderZZ() {
Stack < Node > stck=new Stack<>();
stck.add(this.root);
Stack < Node > stck1=new Stack<>();
int lev=0;
while(!stck.isEmpty()){
Node n=stck.pop();
System.out.print(n.data+" ");
if(lev%2==0){
if(n.right!=null){stck1.push(n.left);}
if(n.left!=null){stck1.push(n.right);}
}else{
if(n.right!=null){stck1.push(n.right);}
if(n.left!=null){stck1.push(n.left);}
}if(stck.isEmpty()){
stck=stck1;
Stack<Node> stck2=new Stack<>();
stck1=stck2;
lev++;
}
}
}
}
}