# Inserting a node in Binary Search Tree

## Algorithm

If an element to be inserted

First create a new node.

Define a node having some data, references to its left and right child nodes. Always Insert a new node as a leaf node
2.  If the data to be inserted is less than the root data, insert in left subtree in a recursive manner by making root to root->left
3.  If the data to be inserted is greater than the root data, insert in right subtree in a recursive manner by making root to root->right.

Time Complexity

The worst case time complexity of a Insertion operation O(h) is h. where h is height of Binary Search Tree.

Figure :

Inserting value 8 in the given Tree

## C++ Program

``````#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct Node {
int data;
Node* left;
Node* right;
};

// Function to create a new Node
Node* NewNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* Insert(Node* root,int data) {
if(root == NULL) { // empty tree
root = NewNode(data);
}
// if data to be inserted is lesser, insert in left subtree in a recursive manner.
else if(data <= root->data) {
root->left = Insert(root->left,data);
}
// else, insert in right subtree in a recursive manner.
else {
root->right = Insert(root->right,data);
}
//return the root pointer
return root;
}
int main() {
Node* root = NULL;  // Creating an empty tree

/* Forming a Tree with values 20,40,30,60,10 */

root = Insert(root,20);
root = Insert(root,40);
root = Insert(root,30);
root = Insert(root,60);
root = Insert(root,10);

cout<<"values have been inserted successfully";

}``````

Scroll to Top