Home » Data Structure

Insertion in Binary Search Tree (BST)

Insertion in Binary Search Tree: Here, we will learn how to insert a Node in Binary Search Tree? In this article you will find algorithm, example in C++. Submitted by Abhishek Jain, on July 30, 2017

Binary Search Tree is one of the most important data structures in computer science.

This data structure enables one to search for and find an element with an average running time f(n)=O(log₂ n). It also enables one to insert and delete (Deletion in Binary Search Tree) elements. This structure contrasts with the help of array and linked list.

Suppose T is a binary tree. Then T is called a binary search tree if each Node N of tree T has the following property: The value at N is greater than every value in the left subtree of N and is less than every value in the right subtree of N. (It is not difficult to see that the property guarantees that the inorder traversal of T will yield a sorted listing of the elements of T.)

Algorithm (Outline):

Suppose an ITEM of information is given. The following algorithm inserts ITEM as a new node in its appropriate place in the tree.

(a) Compare ITEM with the root node N of the tree.
    (i) If  ITEM< N , Proceed to the left Child of N.
    (ii) If ITEM > N, proceed to the right child of N.

(b)Repeat Step (a) until one of the following occurs:
    (i) We meet a node N such that ITEM=N. In this case the search is successful.
    (ii) We meet an empty subtree, which indicates that the search is unsuccessful, 
         and we insert ITEM in place of the empty subtree.

Consider the program:

#include<iostream>
using namespace std;

struct node
{
	int data;
	node* left;
	node* right;
};

struct node* getNode(int data)
{
	node* newNode=new node();
	newNode->data=data;
	newNode->left=NULL;
	newNode->right=NULL;
	return newNode;
}

void inorder(struct node* root)
{
    if (root != NULL)
     {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

struct node* Insert(struct node* root, int data)
{
	if (root == NULL)
		return getNode(data);

	if (data < root->data)
		root->left  = Insert(root->left, data);
	else if (data > root->data)
		root->right = Insert(root->right, data);

	return root;
}

int main()
{  
	node* root=NULL;
	root=Insert(root,20);
	Insert(root,15);
	Insert(root,25);
	Insert(root,18);
	Insert(root,10);
	Insert(root,16);
	Insert(root,19);
	cout<<"Before Insertion: ";
	cout<<"\nInorder: ";
	inorder(root);
	cout<<endl;

	root=Insert(root,17);
	cout<<"\nNode Inserted"<<endl;

	cout<<"\nAfter Insertion: ";
	cout<<"\nInorder: ";
	inorder(root);
	cout<<endl;

	return 0;
}

Output

Before Insertion:
Inorder: 10 15 16 18 19 20 25
Node Inserted
After Insertion:
Inorder: 10 15 16 17 18 19 20 25