## Saturday, June 7, 2014

### Binary Tree Traversal using Recursive and Non-Recursive Methods [Java]

This program takes user input into a binary tree and the traverses the tress displaying the values using recursive and non recursive functions (Non recursive function for Inorder traversal):

Suppose the user inputs (-999 is taken as an end marker for input):
14 15 4 9 7 18 3 5 16 4 20 17 9 14 5 -999

The output of the program using both methods is (for Inorder traversal):
3 4 4 5 5 7 9 9 14 14 15 16 17 18 20
Java Code:

```import java.util.Scanner;

class nodetype{
public int info;
public nodetype left;
public nodetype right;
}

public class NonRecursiveInorderTreeTraversal {

//General tree construction code
static nodetype getnode(){
return new nodetype();
}

static nodetype maketree(int x){
nodetype p = getnode();
p.info = x;
p.left = null;
p.right = null;
return p;
}

static void setleft(nodetype p, int x){
if(p==null)
System.out.println("void insertion\n");
else if(p.left != null)
System.out.println("invalid insertion\n");
else p.left = maketree(x);
}

static void setright(nodetype p, int x){
if(p==null)
System.out.println("void insertion\n");
else if(p.right != null)
System.out.println("invalid insertion\n");
else
p.right = maketree(x);
}

/* Traversal in preorder, inorder and postorder */
static void pretrav(nodetype tree){
if(tree!=null){
System.out.print(tree.info+" ");
pretrav(tree.left);
pretrav(tree.right);
}
}

static void intrav(nodetype tree){
if(tree!=null){
intrav(tree.left);
System.out.print(tree.info+" ");
intrav(tree.right);
}
}

static void posttrav(nodetype tree){
if(tree!=null){
posttrav(tree.left);
posttrav(tree.right);
System.out.print(tree.info+" ");
}
}
/***   ***/

private static int MAXSTACK = 100;
```
```     //Code for the stack used
static class stack{
int top;
nodetype[] item = new nodetype[MAXSTACK];

{
top = 0;
item = new nodetype[MAXSTACK];
}

void push(nodetype it){
if(top<MAXSTACK)
item[top++] = it;
else
System.out.println("Stack Overflow!");
}
nodetype pop(){
if(top!=0)
return item[--top];
else
System.out.println("Nothing to pop!");
return null;
}
boolean empty(){
if(top==0){
return true;
}
return false;
}
}
```
```    //Non Recursive traversal method (inorder) using stack

static void intrav2(nodetype tree){
stack s = new stack();
s.top = 0;

nodetype p = tree;
do{
/*
travel down left branches as far as possible
saving pointers to nodes passed
*/
while(p!=null){
s.push(p);
p = p.left;
} /*end while*/

/*check if finished */
if(!s.empty()){
/* at this point the left subtree is empty */
p = s.pop();
System.out.print(p.info+" ");  /*visit the root*/
p = p.right;                   /*traverse right subtree*/
} /*end if*/
}while(!s.empty() || p!= null);
}/* end funtion */

public static void main(String[] args){
nodetype ptree;
nodetype p = null, q;
int number;

System.out.println("Binary Tree Traversal\n\n");
System.out.println("Enter numbers :");
Scanner scan = new Scanner(System.in);
number = scan.nextInt();

ptree = maketree(number);

while((number=scan.nextInt())!=-999){
p = q = ptree;
while(q!=null){
p=q;
if(number<p.info)
q = p.left;
else if(number>=p.info)
q = p.right;
}

if (number<p.info)
setleft(p, number);
else if(number>=p.info)
setright(p, number);
}

System.out.println("\nUsing recursive function intrav: ");
intrav(ptree);
System.out.println("\nUsing non recursive function intrav2: ");
intrav2(ptree);
}
}```