# 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. ## 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 6Inorder Traversal after insertion3 2 7 1 5 4 6`