Tutorialspoint.dev

Insertion in a Binary Tree in level order

Given a binary tree and a key, insert the key into the binary tree at first position available in level order.



The idea is to do iterative 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 new key as right child. We keep traversing the tree until we find a node whose either left or right is empty.

C++

// C++ program to insert element in binary tree
#include <iostream>
#include <queue>
using namespace std;
  
/* A binary tree node has key, pointer to left child
and a pointer to right child */
struct Node {
    int key;
    struct Node* left, *right;
};
  
/* function to create a new node of tree and r
   eturns pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
  
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
  
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
  
/*function to insert element in binary tree */
void insert(struct Node* temp, int key)
{
    queue<struct Node*> q;
    q.push(temp);
  
    // Do level order traversal until we find
    // an empty place. 
    while (!q.empty()) {
        struct Node* temp = q.front();
        q.pop();
  
        if (!temp->left) {
            temp->left = newNode(key);
            break;
        } else
            q.push(temp->left);
  
        if (!temp->right) {
            temp->right = newNode(key);
            break;
        } else
            q.push(temp->right);
    }
}
  
// Driver code
int main()
{
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
  
    cout << "Inorder traversal before insertion:";
    inorder(root);
  
    int key = 12;
    insert(root, key);
  
    cout << endl;
    cout << "Inorder traversal after insertion:";
    inorder(root);
  
    return 0;
}

Java

// Java program to insert element in binary tree
import java.util.LinkedList;
import java.util.Queue;
public class GFG {
       
    /* A binary tree node has key, pointer to 
    left child and a pointer to right child */
    static class Node {
        int key;
        Node left, right;
          
        // constructor
        Node(int key){
            this.key = key;
            left = null;
            right = null;
        }
    }
    static Node root;
    static Node temp = root;
      
    /* Inorder traversal of a binary tree*/
    static void inorder(Node temp)
    {
        if (temp == null)
            return;
       
        inorder(temp.left);
        System.out.print(temp.key+" ");
        inorder(temp.right);
    }
       
    /*function to insert element in binary tree */
    static void insert(Node temp, int key)
    {
        Queue<Node> q = new LinkedList<Node>();
        q.add(temp);
       
        // Do level order traversal until we find
        // an empty place. 
        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();
       
            if (temp.left == null) {
                temp.left = new Node(key);
                break;
            } else
                q.add(temp.left);
       
            if (temp.right == null) {
                temp.right = new Node(key);
                break;
            } else
                q.add(temp.right);
        }
    }
       
    // Driver code
    public static void main(String args[])
    {
        root = new Node(10);
        root.left = new Node(11);
        root.left.left = new Node(7);
        root.right = new Node(9);
        root.right.left = new Node(15);
        root.right.right = new Node(8);
       
        System.out.print( "Inorder traversal before insertion:");
        inorder(root);
       
        int key = 12;
        insert(root, key);
       
        System.out.print(" Inorder traversal after insertion:");
        inorder(root);
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program to insert element in binary tree 
class newNode(): 
  
    def __init__(self, data): 
        self.key = data
        self.left = None
        self.right = None
          
""" Inorder traversal of a binary tree"""
def inorder(temp):
  
    if (not temp):
        return
  
    inorder(temp.left) 
    print(temp.key,end = " ")
    inorder(temp.right) 
  
  
"""function to insert element in binary tree """
def insert(temp,key):
  
    q = [] 
    q.append(temp) 
  
    # Do level order traversal until we find 
    # an empty place. 
    while (len(q)): 
        temp = q[0
        q.pop(0
  
        if (not temp.left):
            temp.left = newNode(key) 
            break
        else:
            q.append(temp.left) 
  
        if (not temp.right):
            temp.right = newNode(key) 
            break
        else:
            q.append(temp.right) 
      
# Driver code 
if __name__ == '__main__':
    root = newNode(10
    root.left = newNode(11
    root.left.left = newNode(7
    root.right = newNode(9
    root.right.left = newNode(15
    root.right.right = newNode(8
  
    print("Inorder traversal before insertion:", end = " ")
    inorder(root) 
  
    key = 12
    insert(root, key) 
  
    print() 
    print("Inorder traversal after insertion:", end = " ")
    inorder(root)
  
# This code is contributed by SHUBHAMSINGH10


Output:

Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter