Insertion in a Binary Tree (Level Order)

January 24, 2021

Insertion In A Binary Tree

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. In this article, Queue data structure is used to add a node.

C++ Program To Insert In A Binary Tree

Prerequisite Knowledge:

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

 

C++ Program To Insert A Node In A BInary Tree

Algorithm:

  1. Create a queue q.
  2. If root is NULL, add node and return.
  3. Else continue until q is not empty.
  4. If a child does not exists, add the node there.
  5. Otherwise add the node to the leftmost node.

Code:

#include<bits/stdc++.h> 
using namespace std; 
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
void print_level_order(Tree * root) {
    if (root == NULL) return;
    queue <Tree *> q;
    q.push(root);
    while (!q.empty()) {
        cout << q.front() -> data << ” “;
        if (q.front() -> left != NULL) q.push(q.front() -> left);
        if (q.front() -> right != NULL) q.push(q.front() -> right);
        q.pop();
    }
}
Tree* insert(Tree* root, int key) {
    // If empty add the node
    if (root == NULL) {
        Tree * temp = new Tree(key);
        return temp;
    }
    queue <Tree *> q;
    // To check whether tree is perfect tree or not
    bool ok = false;
    while (!q.empty()) {
        Tree* temp = q.front();
        // If null add to the left subtree
        if (temp -> left != NULL) {
            q.push(temp -> left);
        }
        else {
            Tree* add = new Tree(key);
            temp -> left = add;
            ok = true;
            break;
        }
        // If null add to the right subtree
        if (temp -> right != NULL) {
            q.push(temp -> right);
        }
        else {
            Tree* add = new Tree(key);
            temp -> right = add;
            ok = true;
            break;
        }
    }
    if (!ok) {
        Tree* temp = root;
        while (temp -> left != NULL) {
            temp = temp -> left;
        }
        Tree* add = new Tree(key);
        temp -> left = add;
    }
    return root;
} 
int main() {
    Tree *root = new Tree(10);
    root -> left = new Tree(20);
    root -> right = new Tree(30);
    root -> left -> left = new Tree(40);
    root -> left -> right = new Tree(50);
    cout << “Before Adding \n“;
    print_level_order(root);
    cout << endl;
    root = insert(root,10);
    cout << “After Adding \n“;
    print_level_order(root); 
    return 0;
}

 

Output:

Before Adding 
10 20 30 40 50 
After Adding 
10 20 30 40 50 10

 

Time Complexity To Insert Element In A Binary Tree

Time Complexity

O(n)

Space Complexity

O(1)