Thursday, December 10, 2015

InOrder Traversal of Binary Search Tree using Stack in Java

import java.util.ArrayList;


public class BST_Impl {
BST_Node root=null;

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 10, 4, 0, 34, 23, -2,-2, 5, 12, 9, 15, };
BST_Impl tree = new BST_Impl();
for (int i = 0; i < arr.length; i++) {
tree.insert(new BST_Node(arr[i]));

}




}

public void inorder_ByStack(BST_Node root) {
Stack_BST_IMPL stack=new Stack_BST_IMPL();
ArrayList list=new ArrayList();
BST_Node temp=root;
while(!stack.isEmpty()||temp!=null) {
if(temp!=null) {
stack.push(new Stack_Node(temp));
temp=temp.left;
}else {
Stack_Node node= stack.pop();
list.add(node.value.value);
temp=node.value.right;
}

}

System.out.println(list);
}



public void insert(BST_Node node) {
BST_Node temp=root;
if(root==null) {
root=node;
}else {
while(temp!=null) {  //inserting as  leave of a node
if(temp.value>node.value) {
if(temp.left==null) {
temp.left=node;
break;
}
temp=temp.left;
}else if(temp.value
if(temp.right==null) {
temp.right=node;
break;
}
temp=temp.right;
}else {
System.out.println("cannot enter equal number:"+temp.value);
break;
}
}

}

}

}



class BST_Node{
BST_Node left;
BST_Node right;
int value;

public BST_Node( int value) {
this.value=value;
}

}

class Stack_Node{
BST_Node value;
Stack_Node next;

public Stack_Node(BST_Node value) {
this.value=value;
}


}

class Stack_BST_IMPL{
int size=0;
Stack_Node top=null;

void push(Stack_Node node) {
if(top==null) {
top=node;
}else {
node.next=top;
top=node;
}
size++;

}

public Stack_Node pop() {
Stack_Node temp;
temp=top;
if(top!=null) {
top=top.next;
temp.next=null;
size--;
}
return temp;

}

public boolean isEmpty() {
if(size==0) {
return true;
}

return false;
}


}

No comments:

Post a Comment