Insertion Operation in Binary Search Tree(BST)

For inserting an element into a Binary Search Tree, first we have to look the exact location for that element. finding the location means where the new element will place in binary search tree.
for searching the exact location, we will follow the Binary search tree definition. if new element is already available then there is no need to insert, otherwise insert at exact location.

Working Process

Code Implementation

#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
struct BinarySearchTreeNode              // Node Structure Initialization
{
	int  data;                           // for data element
	struct BinarySearchTreeNode* left;   // for storing the address of left child
	struct BinarySearchTreeNode* right;  // for storing the address of right child
};
// Insert method.
void Insert(struct BinarySearchTreeNode* rootNode,int NewElement)
{
	//NewNode Initilization for NewElement
	struct BinarySearchTreeNode* NodeForNewElement = (struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode));
	if (NodeForNewElement == NULL)
	{
		std::cout << "Sorry Memory is not initialized for NewElement";
		return;
	}
	if (rootNode!=NULL)
	{
		while (rootNode)
		{
			if (rootNode->data >= NewElement)
				rootNode = rootNode->left;
			else
				rootNode = rootNode->right;
		}
		rootNode = NodeForNewElement;
		NodeForNewElement->data = NewElement;
		NodeForNewElement->left = NodeForNewElement->right = NULL;
		std::cout << NewElement << " has been inserted at exact location ";
	}
	else
	{
		rootNode = NodeForNewElement;
		rootNode->data = NewElement;
		std::cout << NewElement << " has been inserted at exact location ";
	}
}
int main()
{
	//initialize 5 node to create the binary tree.
	struct BinarySearchTreeNode* Sixty = (struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode));
	struct BinarySearchTreeNode* Fourty = (struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode));
	struct BinarySearchTreeNode* Ninty = (struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode));
	struct BinarySearchTreeNode* ThirtFive = (struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode));
	struct BinarySearchTreeNode* Fifty = (struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode));
	struct BinarySearchTreeNode* Seventy = (struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode));
	//address arrangement.
	Sixty->left = Fourty;
	Sixty->right = Ninty;
	Fourty->left = ThirtFive;
	Fourty->right = Fifty;
	Ninty->left = Seventy;
	//leaf node has zero child.
        ThirtFive->left = NULL;
	ThirtFive->right = NULL;
	Fifty->left = NULL;
	Fifty->right = NULL;
	Seventy->left = NULL;
	Seventy->right = NULL;
        Ninty->right = NULL;
	//Data Initilization.
	Sixty->data = 60;
	Fourty->data = 40;
	Ninty->data = 90;
	ThirtFive->data = 35;
	Fifty->data = 50;
	Seventy->data = 70;
	// call the function to insert the NewElement
	Insert(Sixty,48);
	_getch();
	return 0;
}

 Time & Space Complexity

• Time Complexity will be O(n), and Space Complexity will be O(1).