Wednesday, December 16, 2015

Binary Tree Level order Traversal in java

import java.util.ArrayList;
import java.util.LinkedList;


public class BST_Impl {
BST_Node root=null;


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]));
}

System.out.println("Level order traversal:");
tree.levelOrderTraversal(tree.root);


}

public void levelOrderTraversal(BST_Node root) {
ArrayList> orderList=new ArrayList>();
ArrayList orderValues=new ArrayList();

LinkedList curr=new LinkedList(); //maintain a queue of all nodes on current level.
LinkedList next=new LinkedList(); /*maintain a queue of all the nodes which are available in the next level of the current level, ie child of current level node */
curr.add(root);

while(!curr.isEmpty()) {
BST_Node node=(BST_Node)curr.remove();
if(node.left!=null) {
next.add(node.left);
}
if(node.right!=null) {
next.add(node.right);
}

orderValues.add(node.value);
if(curr.isEmpty()) {
orderList.add(orderValues);
curr=next;
next=new LinkedList();
orderValues=new ArrayList();


}

}

System.out.println(orderList);

}




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;
}

}

No comments:

Post a Comment