Insert node in binary search tree

Insert node in binary search tree

To start binary search tree sessions, let us understand what is binary search and how can we insert node in binary search tree?

First of all, what is a binary search tree? A binary search tree is collection of nodes where each node has maximum two children. Children follow a specific property : left child of node will be smaller and right child will be greater than node. For example, below tree is a binary search tree.

insert node in binary search tree

Where as this one is not. Why?

insert a node in binary search tree

This specific property of binary search tree helps us solve many problems on binary search tree. As whatever is true for entire BST is also true for left as well as right subtree, we can use recursion to arrive at the solution. Second, divide and conquer can be easily applied as left and right subtrees are exclusive sets and based on requirements, we can easily discard one of it or solve problem separately for left and right subtree and then combine solutions to come to solution for entire tree.

How coming to our first task : How to insert node in binary search tree?

There are two cases: Either tree is empty and this is the first node being inserted. Well, it’s simplest case, allocate node and return it.

Second case is when there is a tree and new node is inserted in it. Here, we have to first find right place where new node should be inserted and then link it with it’s parent’s left or right child.

Algorithm to insert node in binary search tree

1. Check if there is a root node. That means tree is not empty.
2. Now, check value to be inserted is less than root? 
   2.1 If yes, move down to left child. 
   2.2 If no, move down to right child. 
3. Repeat step 2 till you cannot go further down, that means even if value is less than currentNode, but there is no left child or value is greater than current node but there is no right child.  
4. Allocate a new node with given value. 
5. Set left or right pointer in the last node which was not null to point to new node.

Let’s take an example and see what does this algorithm do? We have to insert a new node with value 18.

insert node in binary search tree

First, we check that root is not null. Check if new value is less or greater than current node i.e 30. It is less, so move to left child. Again, left child is not null, check if new value is less or greater than current node’s value i.e 20. It is less than move to left child which is 15. Again check, in this case value to be inserted is greater than current node value. So move down to right child. At this point there is no right child of 10, hence we allocate a new node with value 12 and set right child of 10 to point to new node.

Implementation wise, it’s pretty simple. At each node, we are either discarding it’s left or right subtree and continuing the same problem of insertion of node in one of the subtree. So can be easily implemented using recursion. All we need to take care is of termination condition, which is very easy. Whenever, subtree passed is empty, create a node and return it. The parent node should take care of assigning correct pointer to point to this node.

struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
 
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
 
	return 0;
}

Complexity insertion algorithm in binary search tree is O(N). It’s usual misconception that complexity of insertion in BST is O(log N). Insertion complexity is O(log N) when binary search tree is balanced. In case BST is completely skewed, worst case complexity becomes O(N).

We can use this insert method to create an entire binary search tree from scratch. Complexity of creating a BST with N nodes will be O(N2). Why?

Please let me know in case there is something wrong or missing. Sharing is caring.

For more linked lists problems : Linked list problems