Deletion of a node from Binary Search Tree

To delete a node from a binary search tree, the method to be used depends on whether a node to be deleted has one child, two children, or no children.
 
Deletion of a node with two children
Consider the binary search tree shown in following Figure.

To delete a node printed to by x, we start by letting y be a pointer to the node that is the root of the node pointed to by x. We store the pointer to the left child of the node pointed to by x in a temporary pointer temp. We then make the left child of the node pointed to by y the left child of the node pointed to by x. We then traverse the tree with the root as the node pointed to by temp to get its right leaf, and make the right child of this right leaf the right child of the node pointed to by x, as shown in following Figure.

Another method is to store the pointer to the right child of the node pointed to by x in a temporary pointer temp. We then make the left child of the node pointed by y to be the right child of the node pointed to by x. We then traverse the tree with the root as the node pointed to by temp to get its left leaf, and make the left child of this left leaf the left child of the node pointed to by x, as shown in following Figure.

Deletion of a Node with One Child
Consider the binary search tree shown in following Figure.

If we want to delete a node pointed to by x, we can do that by letting y be a pointer to the node that is the root of the node pointed to by x. Make the left child of the node pointed to by y the right child of the node pointed to by x, and dispose of the node pointed to by x, as shown in following Figure.

Deletion of a Node with No Child
Consider the binary search tree shown in following Figure.

Set the left child of the node pointed to by y to NULL, and dispose of the node pointed to by x, as shown in following Figure.

Example

#include <stdio.h>
#include <stdlib.h>
struct tnode {
	int data;
	struct tnode *lchild, *rchild;
};
/* A function to get a pointer to the node whose data value is given
 as well as the pointer to its root */
struct tnode *getptr(struct tnode *p, int key, struct tnode **y) {
	struct tnode *temp;
	if (p == NULL)
		return (NULL);
	temp = p;
	*y = NULL;
	while (temp != NULL) {
		if (temp->data == key)
			return (temp);
		else {
			*y = temp; /*store this pointer as root */
			if (temp->data > key)
				temp = temp->lchild;
			else
				temp = temp->rchild;
		}
	}
	return (NULL);
}

/* A function to delete the node whose data value is given */
struct tnode *delete(struct tnode *p, int val) {
	struct tnode *x, *y, *temp;
	x = getptr(p, val, &y);
	if (x == NULL) {
		printf("The node does not exists\n");
		return (p);
	} else {
		/* this code is for deleting root node*/
		if (x == p) {
			temp = x->lchild;
			y = x->rchild;
			p = temp;
			while (temp->rchild != NULL)
				temp = temp->rchild;
			temp->rchild = y;
			free(x);
			return (p);
		}
		/* this code is for deleting node having both children */
		if (x->lchild != NULL && x->rchild != NULL) {

			if (y->lchild == x) {
				temp = x->lchild;
				y->lchild = x->lchild;
				while (temp->rchild != NULL)
					temp = temp->rchild;
				temp->rchild = x->rchild;
				x->lchild = NULL;
				x->rchild = NULL;
			} else {
				temp = x->rchild;
				y->rchild = x->rchild;
				while (temp->lchild != NULL)
					temp = temp->lchild;
				temp->lchild = x->lchild;
				x->lchild = NULL;
				x->rchild = NULL;
			}

			free(x);
			return (p);
		}
		/* this code is for deleting a node with on child*/
		if ((x->lchild == NULL) && (x->rchild != NULL)) 
        {
			if (y->lchild == x)
				y->lchild = x->rchild;
			else
				y->rchild = x->rchild;
			x->rchild = NULL;
			free(x);
			return (p);
		}
		if (x->lchild != NULL && x->rchild == NULL) {
			if (y->lchild == x)
				y->lchild = x->lchild;
			else
				y->rchild = x->lchild;
			x->lchild = NULL;
			free(x);
			return (p);
		}
		/* this code is for deleting a node with no child*/
		if (x->lchild == NULL && x->rchild == NULL) {
			if (y->lchild == x)
				y->lchild = NULL;
			else
				y->rchild = NULL;
			free(x);
			return (p);
		}
	}
}
/*an iterative function to print the binary tree in inorder*/
void inorder1(struct tnode *p) {
	struct tnode *stack[100];
	int top;
	top = -1;
	if (p != NULL) {
		top++;
		stack[top] = p;
		p = p->lchild;
		while (top >= 0) {
			while (p != NULL)/* push the left child onto stack*/
			{
				top++;
				stack[top] = p;
				p = p->lchild;
			}
			p = stack[top];
			top--;
			printf("%d\t", p->data);
			p = p->rchild;
			if (p != NULL) /* push right child*/
			{
				top++;
				stack[top] = p;
				p = p->lchild;
			}
		}
	}
}
/* A function to insert a new node in binary search 
 * tree to get a tree created*/
struct tnode *insert(struct tnode *p, int val) {
	struct tnode *temp1, *temp2;
	if (p == NULL) {
		p = (struct tnode *) malloc(sizeof(struct tnode)); 
		/* insert the new node as root node*/
		if (p == NULL) {
			printf("Cannot allocate\n");
			exit(0);
		}
		p->data = val;
		p->lchild = p->rchild = NULL;
	} else {
		temp1 = p;
		/* traverse the tree to get a pointer to that node 
		 * whose child will be the newly created node*/
		while (temp1 != NULL) {
			temp2 = temp1;
			if (temp1->data > val)
				temp1 = temp1->lchild;
			else
				temp1 = temp1->rchild;
		}
		if (temp2->data > val) {
			temp2->lchild = (struct tnode*) malloc(sizeof(struct tnode));
			/*inserts the newly created node
			as left child*/
			temp2 = temp2->lchild;
			if (temp2 == NULL) {
				printf("Cannot allocate\n");
				exit(0);
			}
			temp2->data = val;
			temp2->lchild = temp2->rchild = NULL;
		} else {
			temp2->rchild = (struct tnode*) malloc(sizeof(struct tnode));
			/*inserts the newly created node
			as left child*/
			temp2 = temp2->rchild;
			if (temp2 == NULL) {
				printf("Cannot allocate\n");
				exit(0);
			}
			temp2->data = val;
			temp2->lchild = temp2->rchild = NULL;
		}
	}
	return (p);
}

int main() {
	struct tnode *root = NULL;
	int n, x;
	printf("Enter the number of nodes in the tree\n");
	scanf("%d", &n);
	while (n -- > 0)
	{
		printf("Enter the data value\n");
		scanf("%d", &x);
		root = insert(root, x);
	}
	printf("The created tree is :\n");
	inorder1(root);
	printf("\n Enter the value of the node to be deleted\n");
	scanf("%d", &n);
	root = delete(root, n);
	printf("The tree after deletion is \n");
	inorder1(root);
	getchar();
	return 0;
}

Explanation
This program first creates a binary tree with a specified number of nodes with their respective data values. It then takes the data value of the node to be deleted, obtains a pointer to the node containing that data value, and obtains another pointer to the root of the node to be deleted. Depending on whether the node to be deleted is a root node, a node with two children a node with only one child, or a node with no children, it carries out the manipulations as discussed in the section on deleting a node. After deleting the specified node, it returns the pointer to the root of the tree.
 
Input: 1. The number of nodes that the tree to be created should have
2. The data values of each node in the tree to be created
3. The data value in the node to be deleted
 
Output: 1. The data values of the nodes in the tree in inorder before deletion
2. The data values of the nodes in the tree in inorder after deletion
 
Example
Input: 1. The number of nodes taht the created tree should have = 5
2. The data values of the nodes in the tree to be created are: 10, 20, 5, 9, 8
3. The data value in the node to be deleted = 9
 
Output: 1.5 8 9 10 20
2 5 8 10 20
 

Applications of Binary Search Trees

One of the applications of a binary search tree is the implementation of a dynamic dictionary. This application is appropriate because a dictionary is an ordered list that is required to be searched frequently, and is also required to be updated (insertion and deletion mode) frequently. So it can be implemented by making the entries in a dictionary into the nodes of a binary search tree. A more efficient implementation of a dynamic dictionary involves considering a key to be a sequence of characters, and instead of searching by comparison of entire keys, we use these characters to determine a multi-way branch at each step. This will allow us to make a 26-way branch according to the first letter, followed by another branch according to the second letter and so on.
 

General Comments on Binary Trees

• Trees are used to organize a collection of data items into a hierarchical structure.
• A tree is a collection of elements called nodes, one of which is distinguished as the root, along with a relation that places a hierarchical structure on the node.
• The degree of a node of a tree is the number of descendants that node has.
• A leaf node of a tree is a node with a degree equal to 0.
• The degree of a tree is the maximum of the degree of the nodes of the tree.
• The level of the root node is 1, and as we descend the tree, we increment the level of each node by 1.
• Depth of a tree is the maximum value of the level for the nodes in the tree.
• A binary tree is a special case of tree, in which no node can have degree greater than 2.
• The maximum number of nodes at level i in a binary tree is 2i−1.
• The maximum number of nodes in a binary tree of depth k is 2k−1.
• A complete binary tree of depth k is a tree with n nodes in which these n nodes can be numbered sequentially from 1 to n.
• If a binary tree is a complete binary tree, it can be represented by an array capable of holding n elements where n is the number of nodes in a complete binary tree.
• Inorder, preorder, and postorder are the three commonly used traversals that are used to traverse a binary tree.
• In inorder traversal, we start with the root node, visit the left subtree first, then process the data of the root node, followed by that of the right subtree.
• In preorder traversal, we start with the root node. First we process the data of the root node, then visit the left subtree, then the right subtree.
• In postorder traversal, we start with the root node, visit the left subtree first, then visit the right subtree, and then process the data of the root node.
• To construct a unique binary tree, we require two orders of traversal, in which one has to be inorder; the other could be preorder or postorder.
• A binary search tree is an important search structure that is dynamic and allows a search by using O(log2n) steps.