# 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.