class Node
{
Object data;
Node left;
Node right;
Node( Object d ){ 
data = d;
}
}
class BinaryTree{
Object tree[];
int maxSize;
java.util.Stack<Node> stack = new java.util.Stack<Node>();
BinaryTree( Object a[], int n ){
maxSize = n;
tree = new Object[maxSize];
for( int i=0; i<maxSize; i++ )
tree[i] = a[i];
}
public Node buildTree( int index ){
Node p = null;
if( tree[index] != null ){
p = new Node(tree[index]); 
p.left = buildTree(2*index+1);
p.right = buildTree(2*index+2);
}return p;
}
//Recursive methods
public void recursiveInorder(Node p){
if( p != null ){
recursiveInorder(p.left);
System.out.print(p.data + " ");
recursiveInorder(p.right);
}
}
public void recursivePreorder(Node p){
if( p != null ){
System.out.print(p.data + " ");
recursivePreorder(p.left);
recursivePreorder(p.right);
}
}
public void recursivePostorder(Node p){
if( p != null ){
recursivePostorder(p.left);
recursivePostorder(p.right);
System.out.print(p.data + " ");
}
}
//Non-Recursive methods
public void nonRecursiverecursivePreorder(Node p){
if(p == null ){
System.out.println("Tree is empty");
return;
}
stack.push(p);
while( !stack.isEmpty() ){
p = stack.pop();
if( p != null ){
System.out.print(p.data + " ");
stack.push(p.right);
stack.push(p.left);
}
}
} 
public void nonRecursiverecursiveInorder(Node p){
if(p == null ){
System.out.println("Tree is empty");
return; 
}
while( !stack.isEmpty() || p != null ){
if( p != null ){
stack.push(p);
p = p.left;
}
else{
p = stack.pop();
System.out.print(p.data + " ");
p = p.right;
}
}
} 
public void nonRecursiverecursivePostorder(Node p){
if(p == null ){
System.out.println("Tree is empty");
return;
}
Node tmp = p;
while( p != null ){
while( p.left != null ){
stack.push(p);
p = p.left;
}
while( p != null && (p.right == null || p.right == tmp )){
System.out.print(p.data + " ");
tmp = p;
if( stack.isEmpty() )
return;
p = stack.pop();
}
stack.push(p);
p = p.right;
}
}
}

class BinaryTreeExample{
public static void main(String args[]){
Object arr[] = {'E', 'C', 'G', 'A', 'D', 'F', 'H',null,'B', null, null, null, null,null, null, null, null, null, null};
BinaryTree bt = new BinaryTree( arr, arr.length );
Node root = bt.buildTree(0); 
System.out.println("Recursive Binary Tree Traversals:");
System.out.print("recursiveInorder: ");
bt.recursiveInorder(root); 
System.out.println();
System.out.print("recursivePreorder: ");
bt.recursivePreorder(root);
System.out.println();
System.out.print("recursivePostorder: ");
bt.recursivePostorder(root);
System.out.println();
System.out.println();
System.out.println("Non-recursive Binary Tree Traversals:");
System.out.print("recursiveInorder: ");
bt.nonRecursiverecursiveInorder(root);
System.out.println();
System.out.print("recursivePreorder: ");
bt.nonRecursiverecursivePreorder(root);
System.out.println();
System.out.print("recursivePostorder: ");
bt.nonRecursiverecursivePostorder(root);
}
}