Binary Search Tree operations in C.

bst_operations.c

#include<stdio.h>
#include<stdlib.h>

struct Node
{
	int data;
	struct Node* next;
	struct Node* prev;
};

struct Node *root = NULL;
struct Node *temp = NULL;

void insert_succ(struct Node* node)
{
	if((temp->data > node->data) && (node->next != NULL))
		insert_succ(node->next);
	else if((temp->data > node->data) && (node->next == NULL))
		node->next = temp;
	if((temp->data < node->data) && (node->prev != NULL))
		insert_succ(node->prev);
	else if((temp->data < node->data) && (node->prev == NULL))
		node->prev = temp;
}

void insertNode()
{
	int el;
	temp = (struct Node*)malloc(sizeof(struct Node));
	
	printf("\nData to be inserted into the node: ");
	scanf("%d", &el);
	temp->data = el;

	temp->next = temp->prev = NULL;

	if(root == NULL)
		root = temp;
	else
		insert_succ(root);
}

void preorder(struct Node* node)
{
	if(node == NULL)
	{
		printf("\nTree is empty!");
		exit(1);
	}
	printf("%d =>", node->data);
	if(node->prev != NULL)
		preorder(node->prev);
	if(node->next != NULL)
		preorder(node->next);
}

void inorder(struct Node *node)
{
    if (root == NULL)
    {
        printf("No elements in a tree to display");
        return;
    }
    if (node->prev != NULL)
        inorder(node->prev);
    printf("%d => ", node->data);
    if (node->next != NULL)
        inorder(node->next);
}

void postorder(struct Node* node)
{
	if(node == NULL)
	{
		printf("\nTree is empty!");
		exit(1);
	}
	if(node->prev != NULL)
		postorder(node->prev);
	if(node->next != NULL)
		postorder(node->next);
	printf("%d =>", node->data);
}

void search_el(struct Node* node, int el)
{
	if(root == NULL)
	{
		printf("\nTree is empty!");
		exit(1);
	}
	// Since the method is being invoked recursively, node becomes null if the element is not found.
	if(node == NULL)
	{
		printf("\nElement not found!");
		return;
	}

	if(el < node->data)
		search_el(node->prev, el);
	else if(el > node->data)
		search_el(node->next, el);
	else if(el == node->data)
	{
		printf("\nElement found!");
	}
}

struct Node* find_succ(struct Node* node)
{
	while(node->prev != NULL)
	{
		node = node->prev;
	}
	return node;
}

struct Node* deleteNode(struct Node* root, int el)
{
	struct Node* temp_node;
	if(root == NULL)
	{	
		printf("\nTree is empty!");
		exit(1);
	}
	else if(el > root->data)
		root->next = deleteNode(root->next, el);
	else if(el < root->data)
		root->prev = deleteNode(root->prev, el);
	else
	{
		if(root->next == NULL && root->prev == NULL)
		{
			free(root);
			root = NULL;
		}
		else if(root->prev == NULL)
		{
			temp_node = root;
			root = root->next;
			free(temp_node);
		}
		else
		{
			temp_node = find_succ(root->next);
			root->data = temp_node->data;
			root->next = deleteNode(root->next, temp_node->data);
		}
	}
	return root;	
}

int main()
{
	int el, cont = 1;
	while(1)
	{
		insertNode();
		printf("\nWant to continue? Enter 1 for Yes: ");
		scanf("%d", &cont);
		if(cont != 1)
			break;
	}

	printf("\nPreorder form: ");
	preorder(root);

	printf("\nInorder form: ");
	inorder(root);

	printf("\nPostorder form: ");
	postorder(root);

	printf("\nData of the node to be searched: ");
	scanf("%d", &el);
	search_el(root, el);

	printf("\nData of the node to be deleted: ");
	scanf("%d", &el);
	deleteNode(root, el);

	printf("\nTree after deleting %d is: ", el);
	preorder(root);
	return 0;
}