Insert a node in Binary Search Tree (BST)

We have a Binary search tree and a key. Insert the key in the binary search tree if not present.

In the above figure, the key to be inserted is 5. We have inserted it in the tree, and the modified tree is shown with the blue circle containing 5.

To be more clearer, let us look at another example:

100 100

/ \ Insert 40 / \

20 500 ---------> 20 500

/ \ / \

10 30 10 30

Approach 1: Recursive

Start the search from the root. If the key to be inserted is less than the root, it will be inserted in the left subtree else right subtree. Follow up until we hit the leaf node, and if there is a vacancy, we put the key at that level.

C++ code:

 #include <iostream>
 using namespace std;
 class BST // Create the BST Tree Structure
     {
     int data; //  node value of BST
     BST *left, *right; // left and right pointers to BST
 public:
     BST(); // Default constructor
     BST(int); // constructor when passed a value
     BST* Insert(BST*, int); // insert a value(key) in the BST
     void Inorder(BST*); // print Inorder traversal of BST
 };
 BST::BST() // Define Default Constructor
     : data(0),
       left(NULL),
       right(NULL)
 {
 }
 BST::BST(int value) // define paramertised Constructor
 {
     data = value;
     left = right = NULL;
 }
 BST* BST::Insert(BST* root, int value) // function to insert the given key
 {
     if (!root) {
         return new BST(value); // if the tree is empty, then the passed key is only the root node
     }
     if (value > root->data) {
         root->right = Insert(root->right, value);
     }
     else {
         root->left = Insert(root->left, value);
     }
     // Return 'root' node, after insertion.
     return root;
 }
 void BST::Inorder(BST* root) // The Inorder traversal
 {
     if (!root) {
         return;
     }
     Inorder(root->left); // in order rule - root--->left
     cout << root->data << endl; // key of root
     Inorder(root->right); // right of root
 }
 int main() // main function
 {
     BST b, *root = NULL;
     root = b.Insert(root, 50);
     b.Insert(root, 30);
     b.Insert(root, 20);
     b.Insert(root, 40);
     b.Insert(root, 70);
     b.Insert(root, 60);
     b.Insert(root, 80);
     b.Inorder(root);
     return 0;
 }

C code:

 #include <stdio.h>
 #include <stdlib.h>
 struct node { // create BST Tree structure
           int key; // Value of BST Node
           struct node *left, *right; // Left and right pointers to BST Node
 };
 struct node* newNode(int item) // Insert value in the tree
 {
           struct node* temp = (struct node*)malloc(sizeof(struct node)); // Allocate memory
           temp->key = item; // Store the value
           temp->left = temp->right = NULL; // LEft and right point to NULL
           return temp;
 }
 void inorder(struct node* root) // This function will print in order of the tree
 {
           if (root != NULL) {
                    inorder(root->left); // in order rule - root--->left
                    printf("%d \n", root->key); // key of root
                    inorder(root->right); // right of root
           }
 }
 struct node* insert(struct node* node, int key) // The function to insert the key in BST
 {
           if (node == NULL) // If tree is not created yet
                    return newNode(key); // create the key as root
           if (key < node->key) // If key is less than node's value
                    node->left = insert(node->left, key); // it will fit in the left subtree
           else if (key > node->key)
                    node->right = insert(node->right, key); // other wise right subtree
           return node; // return the node
 }
 int main() // main function
 {
           struct node* root = NULL;
           root = insert(root, 50); // the root node
           insert(root, 30);
           insert(root, 20);
           insert(root, 40);
           insert(root, 70);
           insert(root, 60);
           insert(root, 80);
                    inorder(root); // print inorder of the tree created after insertion
           return 0;
 }

Output

Time complexity: O(Height of the tree)

DAA: Insert a node in Binary Search Tree