Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: May 29, 2024
Difficulty: Easy

Insertion in Binary Search Tree(BST)

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
insertion into bst

Introduction 

Binary search tree BST is one type of binary tree Data Structure that is either empty, or each node in the tree contains a key and:

 (i) all keys in the left subtree of T are less (numerically or alphabetically) than the key  in the root node of T; 

(ii) all keys in the right subtree of T are greater than the key in the root node of the BST;

(iii) the left and right subtrees of the BST are also binary search trees.

While inserting nodes in a binary search tree, we should be conscious that it should not violate the property of a binary search tree after insertion.

What is insertion in BST?

Insertion in a Binary Search Tree (BST) is the process of adding a new node into the tree while maintaining the BST property. The new node's value is compared with existing nodes, and it is placed as a child of an appropriate parent node based on whether it is smaller or larger. This ensures that the left subtree of any node contains only smaller values, and the right subtree contains only larger values, preserving the ordered structure of the BST.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

How to Insert a value in a Binary Search Tree

Below are the steps to insert a value into a Binary Search Tree (BST):

  1. Start at the Root: Begin at the top of the tree, the root
     
  2. Compare Values: Compare the value you want to insert with the current node's value
     
  3. Go Left or Right: If it's smaller, move to the left else if it's larger, then move to the right
     
  4. Repeat Comparison: Keep comparing and moving left or right until you find a spot where you can't go further because there's no more left or right child
     
  5. Insert the Node: Create a new node with the value to be inserted

Method 1: Iterative method

Algorithm

  • For inserting in the Binary Tree, the value is compared with that of the root.
  • If the given value is lesser than the root’s, then move to root’s left, and it is compared with root’s left child value.
  • If the given value is greater than the root’s, then move to root’s right, and it is compared with root’s right child value.
  • This comparison continues until a leaf node is reached.
  • Then new node is inserted as a left or right child of the leaf node depending on its value.
  • For empty BST, the value is directly inserted as the root’s key.

Implementation in C

#include<bits/stdc++.h>
using namespace std;
 /************* BST node ************/
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };
  
  
  /************* insertion function************/
  TreeNode* insertIntoBST(TreeNode* root, int val) {
    
        TreeNode* curr=root,*node=new TreeNode(val);
        while(curr){


            // curr val greater than val ,new node will be in left subtree



            if(curr->val > val){ 
                if(curr->left){
                    curr=curr->left;
                }else{
                    curr->left=node;
                    break;
                }




       //curr val less than Val, the new node will be in the right subtree
          }else{


         
                if(curr->right){           
                    curr=curr->right;
                }
                else{
                    curr->right=node;
                    break;
                }
            }
        }
        return root?root:node;
    }




/**** function to perform inorder traversal on the BST  ***/
void inorder(TreeNode* root)
{
    if (root == nullptr) {
        return;
    }
 
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}



int main()
{
    int keys[] = {4,2,7,1,3,5};
 
    TreeNode* root = nullptr;
    for (int key: keys) {
        root = insertIntoBST(root, key);
    }
 
    inorder(root);
 
    return 0;
}

 

Complexity Analysis

Time complexity: For the above solution, the time complexity is O(h), where h is the height of the binary search tree. In the worst-case height becomes equal to the number of nodes in the BST(skewed tree).

Space complexity: O(1)

 You can also read about insertion into bst.

Method 2: Recursive method

Algorithm

  • (Base Condition) Examine the root if it is null, create BST node with given value and return the node pointer 
  • If the given value is lesser than the root’s, recursively insert the new node to the left subtree.
  • If the given value is greater than the root’s, recursively insert the new node to the right subtree.

 

Implementation in C

#include<bits/stdc++.h>
using namespace std;


struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };
  
  
  /************* insertion function************/



  TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root){
            TreeNode* newNode=new TreeNode(val);
            return newNode;
        }
        
        //root val greater than val ,  the new node will be in the left subtree
        if(root->val > val){  


            root->left=insertIntoBST(root->left,val);
    
        }
        
        //root val lesser than val, the new node will be in the right subtree
        else{
              root->right=insertIntoBST(root->right,val);


          }
        return root;
    }




/** function to perform inorder traversal on the BST **/
void inorder(TreeNode* root)
{
    if (root == nullptr) {
        return;
    }
 
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}



int main()
{
    int keys[] = {4,2,7,1,3,5};
 
    TreeNode* root = nullptr;
    for (int key: keys) {
        root = insertIntoBST(root, key);
    }
 
    inorder(root);
 
    return 0;
}

 

output :1 2 3 4 5  7

Complexity Analysis

Time complexity: For the above solution, the time complexity is O(h), where h is the height of the binary search tree. In the worst-case, height becomes equal to the number of nodes in the BST(skewed tree).

Space complexity: Due to stack space for recursive calls, space complexity is O(h) at the worst case.

Frequently Asked Questions

What is a Binary Tree?

A tree is called a binary tree if every node has at most two children nodes.  A binary tree node constitutes a left pointer, a right pointer, and a data element. An empty binary tree (with zero nodes) is also a valid binary tree.

How do you insert a value in a BST?

In order to insert a value in BST, we compare the value with nodes, going left if smaller and right if larger. Inserting at a leaf node while maintaining the BST property.

What is insertion and deletion in BST?

Insertion in BST means to add a value while preserving order, and deletion in BST refers to removing a node while maintaining the BST structure.

Can we insert duplicates in BST?

In a standard BST, duplicate values are usually not allowed. Insertion may be ignored or handled differently based on implementation.

Where do insertions happen in a binary search tree?

Insertions in a Binary Search Tree or BST occur at leaf nodes or null positions in the tree. When inserting a new node, the BST is traversed from the root node to find the appropriate position for the new node.

Conclusion

This article covered different methods of how to make insertion in the Binary Search Tree. We have learned about the various algorithms to insert nodes in BSTs, but that’s not enough for us. 

Side by side, we should also learn about searching and deletion operations in  Binary Search Tree.

Recommended Reading: 

Recommended problems -

 

After you've mastered insertion, you should learn how to delete a node in BST. Check out the video below, which covers both the insertion and deletion of a node in BST

Topics covered
1.
Introduction 
2.
What is insertion in BST?
3.
How to Insert a value in a Binary Search Tree
4.
Method 1: Iterative method
4.1.
Algorithm
4.2.
Implementation in C
4.3.
Complexity Analysis
5.
Method 2: Recursive method
5.1.
Algorithm
5.2.
Implementation in C
5.3.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What is a Binary Tree?
6.2.
How do you insert a value in a BST?
6.3.
What is insertion and deletion in BST?
6.4.
Can we insert duplicates in BST?
6.5.
Where do insertions happen in a binary search tree?
7.
Conclusion