Insertion In A Binary Search Tree In C++

Insertion In A Binary Search Tree

A binary search tree is a tree in which the data in left subtree is less than the root and the data in right subtree is greater than the root. In this article, insertion is performed using recursion in C++.

C++ Program To Insert In Binary Search Tree

Rules For Binary Search Tree:

  • Left subtree for any given node will only contain nodes which are lesser than the current node
  • Right subtree for any given node will only contain nodes which are greater than the current node
  • This is valid for all nodes present in BST.
Rules For BST - C++ Program To Insert in Binary Search Tree

Algorithm To Insert In BST:

  1. Input the value of the element to be inserted.
  2. Start from the root.
  3. If the input element is less than current node, recurse for left subtree otherwise for right subtree.
  4. Insert the node wherever NULL is encountered.

 

Algorithm For BST - C++ Program To insert in Binary TRee

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 inorder_traversal (Tree *root) {
    if (root == NULLreturn;
    // Visit Left subtree
    inorder_traversal(root -> left);
      // Print the data
    cout << root -> data << ” “;
    // Visit right subtree
    inorder_traversal(root -> right);
  
}
Tree* insert_node(Tree* rootint x) {
    // If leaf is encountered
    if (root == NULL) {
        Tree *temp = new Tree(x);
        return temp;
    }
    // Recur for left subtree
    if (root -> data > x) {
        root -> left = insert_node(root -> left, x);
    }
    // Recur for right subtree
    else {
        root -> right = insert_node(root -> right , x);
    }
    return root;
    
}
int main() {
    Tree *root = new Tree(15);
    root -> left = new Tree(12);
    root -> right = new Tree(54);
    root -> left -> left = new Tree(8);
    root -> left -> right = new Tree(13);
    root -> left -> left -> left = new Tree(5);
    root -> right -> left = new Tree(20);
    int x = 10;
    insert_node(root, x);
    cout << “Inorder Traversal – “;
    inorder_traversal(root);
    return 0;
}

 

Output:

Inorder Traversal - 5 8 10 12 13 15 20 54 

 

Time Complexity To Insert Element in Binary Search Tree

Time Complexity

O(n)

Space Complexity

O(h)