Insert Node in Binary Tree and Java Program to add a Node in Binary Tree

Insert Node in Binary Tree

---

Let's see how to Insert node in Binary Tree in Java and Java Program to add a Node in Binary Tree. For adding a node, 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.

 

All post below contain examples of adding a Node in Binary tree using different approach,

1. Top Binary tree interview questions in Java
2. Find Kth SMALLEST element in BST(Binary Search Tree)
3. Check whether Binary Tree is foldable or not.
4. Check if two nodes are cousins in a Binary Tree.
5. Get Level/Height of node in binary tree
6. Print nodes at K distance from Leaf node in Binary tree.
7. Construct a Binary Tree from In-order and Post-order traversals.
8. Print Nodes in Top View of Binary Tree.
9. Zig Zag Traversal of Binary Tree.
   

 

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

---

package javabypatel;

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

}

You may also like to see

---

Compress a given string in-place and with constant extra space.

Check whether a given string is an interleaving of String 1 and String 2.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Serialize and Deserialize a Binary Tree

Advanced Multithreading Interview Questions In Java

Enjoy !!!! 

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