Deletion Operation in Binary Search Tree(BST)

Deletion Operation of Binary Search Tree(BST) is something complex , because we are not going to only delete the specific element from Binary Search Tree(BST) but also we consider the correct arrangement of node after deletion operation. There are some cases. see the below Working Process of each cases:

Working Process

• When deleting element has zero child means that is leaf node , then there is no more complex arrangement of node after delete. just delete the node and set NULL to their corresponding parent. See below Diagram :
  

• When deleting element has one child, then there is no more complex arrangement of node after delete. just delete the node and set the child node of deleting element to the parent node of deleting element.

• When deleting element has two child ,then process is something complex. first we have to find the largest element in left subtree of deleting element , and set with the location of deleting element. Now largest element in left subtree of deleting element can have left subtree , So this whole left subtree will be set to the parent of largest element in left subtree of deleting element.

Code Implementation

BSTNode* DeleteInBST(BSTNode* root,int deleting_Element)
{
	struct BSTNode* temp;
	if (root == NULL)
		printf("Sorry Binary Search Tree is Empty.. :");
	else if (deleting_Element < root->data)
		root->left = DeleteInBST(root->left, deleting_Element);
	else if (deleting_Element > root->data)
		root->right = DeleteInBST(root->right,deleting_Element);
	else
	{
		//deleting_Element is founded
		// when two child
		if (root->left && root->right)
		{
			//Find Larget Element in Left Subtree of deleting_Element
			temp = FindMaxInLeftSubtreeOf_deleting_Element(root->left);
			root->data = temp->data;
			root->left = DeleteInBST(root->left,root->data);
		}
		else
		{
			//when one or zero child
			temp = root;
			if (root->left == NULL)
				root = root->right;
			if (root->right == NULL)
				root = root->left;
			//Delete the deleting_Element Node.
			free(temp);
		}
	}
	printf("Now %d is deleted Successfully :", deleting_Element);
}

Time & Space Complexity

• Time Complexity will be O(n).
• Space Complexity will be O(1) for Non-Recursive Implementation.
• Space Complexity will be O(n) for Recursive Implementation.