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
1.  Start with a empty tree by making root Null. 
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";
	
}
Try It


Next > < Prev
Scroll to Top