Home » Algorithm » Binary Tree » Datastructure » Interviews » Java » Insert Node in Binary Tree and Java Program to add a Node in Binary Tree

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

in , , , , - on 07:42:00 - No comments

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,
 

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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.
Categories: , , , ,