Insertion in a Binary Tree (Level Order) in Java

August 25, 2021

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.

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

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