Add a node in Binary Tree and not a Binary Search Tree.

How to add a Node in Binary Tree and not a Binary Search Tree?


To add a Node in a Binary Tree, Let us first fix our protocol of how we are going a insert a node in Binary Tree.

So start scanning a Binary Tree level by level and wherever we encounter vacant position, place a new Node there.

See below image to get better understanding of position of a new Node to insert.
Given a binary tree, we need to add a Node with value 8 marked in dotted lines below in its correct position.



Java Program to insert a Node in Binary Tree and not a Binary Search Tree?


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(){

  addNodeInBinaryTree(rootNode, 1); 
  addNodeInBinaryTree(rootNode, 2); 
  addNodeInBinaryTree(rootNode, 3); 
  addNodeInBinaryTree(rootNode, 4); 
  addNodeInBinaryTree(rootNode, 5); 

  printTreeLevelOrder(rootNode);
 }

 //Iterative way of adding new Node in Binary Tree.
 private void addNodeInBinaryTree(Node rootNode, int data){
  
  if(rootNode==null){
   // No Nodes are Present, create one and assign it to rootNode
   this.rootNode = new Node(data);
  
  }else{
   //Nodes present, So checking vacant position for adding new Node in sequential fashion 
   //Start scanning all Levels (level by level) of a tree one by one until we found a node whose either left or right node is null.
   //For each and every node, we need to check whether Left and Right Node exist? 
   //If exist, then that node is not useful for adding new node but we need to store left and right node of that node for later processing 
   //that is why it is stored in Queue for sequential placement.
   //If not exist, then we found a node, where new node will be placed but not sure on left or right, so check which side is null and place new node there.

   Queue<Node> q = new LinkedList<Node>();
   q.add(rootNode);
   while(!q.isEmpty()){
    Node node = q.poll();

    if(node.getLeft()!=null && node.getRight()!=null){
     q.add(node.getLeft());
     q.add(node.getRight());
    }else{
     if(node.getLeft()==null){
      node.setLeft(new Node(data));
     }else{
      node.setRight(new Node(data));
     }
     break;
    }
   }
  }
  
 }

 private void printTreeLevelOrder(Node rootNode) {
  if(rootNode==null)
   return;

  Queue<Node> q = new LinkedList<Node>();
  q.add(rootNode);
  
  while(!q.isEmpty()){
   Node node = q.poll();
   System.out.print(node.getData() + " ");

   if(node.getLeft()!=null)
    q.add(node.getLeft());

   if(node.getRight()!=null)
    q.add(node.getRight());
  }
 
 }

}


Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment