Insertion in a Binary Tree (Level Order) in Java

Insertion in Binary Tree

Insertion in Binary Tree is being discussed in this article. A binary tree can be defined as a finite set of elements, which can either be empty or have at most two children. Given a tree and a key, add a node in the first available node in the tree. After adding the node, print the level order traversal. 

Insertion in Binary Tree in Java

Binary Tree

  • A Binary Tree is a data structure with maximum of two children for each parent.
  • Level Order Traversal is an example Of Breadth First Search algorithm.
  • Level order is a traversal in which each node is visited in the level before we move to a lower level.
  • Queues are used to find the level order traversal.

Example - Insertion in Binary Tree

Insertion in Binary Tree in Java

Algorithm

  • Iterate level order traversal of the given tree using queue.
  • If we find a node whose left child is empty, we make new key as left child of the node.
  • Else if we find a node whose right child is empty, we make the new key as right child. 
  • Keep traversing the tree until we find a node whose wither left or right child is empty.

Code in Java

import java.util.*;
class Node
{
int value;
Node left, right;

Node (int value)
{
this.value = value;
left = right = null;
}
}

class Solution
{
static Node root;
//static Node temp=root;
public static void inorder (Node ptr)
{
if (ptr == null)
return;
inorder (ptr.left);

System.out.print (ptr.value + " ");
inorder (ptr.right);
}

public static void insert (Node ptr, int item)
{
if (ptr == null)
{
root = new Node (item);
return;
}
Queue < Node > que = new LinkedList < Node > ();
que.add (ptr);

while (!que.isEmpty ())
{
ptr = que.peek ();
que.remove ();
if (ptr.left == null)
{
ptr.left = new Node (item);
break;
}
else
que.add (ptr.left);

if (ptr.right == null)
{
ptr.right = new Node (item);
break;
}
else
que.add (ptr.right);
}
}

public static void main (String[]args)
{
root = new Node (1);
root.left = new Node (2);
root.left.left = new Node (3);
root.right = new Node (4);
root.right.left = new Node (5);
root.right.right = new Node (6);

System.out.println ("Inorder Traversal before Insertion: ");
inorder (root);

int item = 7;
insert (root, item);

System.out.println ("\nInorder Traversal after insertion");

inorder (root);
}
}

Output :

Inorder Traversal before Insertion:
3 2 1 5 4 6
Inorder Traversal after insertion
3 2 7 1 5 4 6