This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Wednesday, 10 December 2014

Add a Node In Binary Tree

package tree;

public class Node{
 
 private Node left;
 private Node right;
 private int data;
 
 public Node(int data){
  this.data=data;
 }

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }
}

package tree;
import java.util.LinkedList;
import java.util.Queue;

public class AddNodeInBinaryTree {
 private Node rootNode;

 public static void main(String[] args) {
  new AddNodeInBinaryTree();
 }

 public AddNodeInBinaryTree(){
  addNode(rootNode, 1); 
  addNode(rootNode, 2); 
  addNode(rootNode, 3); 
  addNode(rootNode, 4); 
  addNode(rootNode, 5); 

  printTreeLevelOrder(rootNode);
 }

 private void printTreeLevelOrder(Node rootNode){
  if(rootNode==null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(rootNode);

  while(!queue.isEmpty()){
   Node obj = (Node)queue.poll();
   System.out.print(obj.getData() + " ");
   if(obj.getLeft()!=null)
    queue.add(obj.getLeft());

   if(obj.getRight()!=null)
    queue.add(obj.getRight());
  }
 } 

 private void addNode(Node rootNode, int data){

  //First check is there any Nodes present.
  if(rootNode==null){
   // No Nodes are Present, create one and assign it to startNode
   Node temp1=new Node(data);
   this.rootNode=temp1;
  }else{
   //Nodes present, So check the proper position where to add New Node.

   //Checking whether Left child and Right child are present for root Node. 
   if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
    //Left and Right Child exist, Also, we need to add ne Node in Sequential Fashion of Left and Right, 
    //We have to scan all Levels one by one to check a proper place for new Node.
    //Also, we for each and every node we need to check whether Left and Right Exist, 
    //So we need to store them for later Processing that is why we introduced Queue.

    Queue<Node> queue = new LinkedList<Node>();
    queue.add(rootNode);

    while(!queue.isEmpty()){
     Node obj = (Node)queue.poll();
     if(obj.getLeft()!=null && obj.getRight()!=null){
      queue.add(obj.getLeft());
      queue.add(obj.getRight());
     }else if(obj.getLeft()==null){
      Node temp1=new Node(data);
      obj.setLeft(temp1);
      break;
     }else{
      Node temp1=new Node(data);
      obj.setRight(temp1);
      break;
     }
    }

   }else{
    // We reach this condition when either Left or Right is Null, but not sure which side is Null.
    if(rootNode.getLeft()==null){
     Node temp1=new Node(data);
     rootNode.setLeft(temp1);
    }else{
     Node temp1=new Node(data);
     rootNode.setRight(temp1);
    }
   }
  }
 }
}

No comments:

Post a Comment