Binary Tree

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

/* Tree structure */
struct tree {
	int data;
	struct tree *left;
	struct tree *right;
} *root = NULL, *node = NULL, *temp = NULL;

/* Function for Insert data into the Tree */
struct tree* insert(int key,struct tree *leaf) {
	if(leaf == 0) {
		struct tree *temp;
		temp = (struct tree *)malloc(sizeof(struct tree));
		temp->data = key;
		temp->left = 0;
		temp->right = 0;
		printf("Data inserted!\n");
		return temp;
	}
	else {
		if(key < leaf->data)
			leaf->left = insert(key,leaf->left);
		else
			leaf->right = insert(key,leaf->right);
	}
	return leaf;					
}

/* Function for search data from Tree */
struct tree* search(int key,struct tree *leaf) {
	if(leaf != NULL) {
		if(key == leaf->data) {
			printf("Data found!\n");
			return leaf;
		}
		else {
			if(key < leaf->data)
				return search(key,leaf->left);
			else
				return search(key,leaf->right);
		}
	}
	else {
		printf("Data not found!\n");
		return NULL;
	}
}
										
/* Function for find minimum value from the Tree */
struct tree* minvalue(struct tree *node) {
	if(node == NULL)
		return NULL;

	/* Go to the left sub tree to find the min element */
	if(node->left)
		return minvalue(node->left);
	else
		return node;									
}

/* Function for find maximum value from the Tree */
struct tree* maxvalue(struct tree *node) {
	if(node == NULL)
		return NULL;

	/* Go to the left sub tree to find the max element */
	if(node->right)
		return maxvalue(node->right);
	else
		return node;									
}

/* Function for print binary tree in Preorder format */
void preorder(struct tree *leaf) {
	if(leaf == NULL)
		return;
	printf("%d\n",leaf->data);
	preorder(leaf->left);
	preorder(leaf->right);									
}

/* Function for print binary tree in Inorder format */
void inorder(struct tree *leaf) {
	if(leaf == NULL)
		return;
	preorder(leaf->left);
	printf("%d\n",leaf->data);
	preorder(leaf->right);									
}

/* Function for print binary tree in Postorder format */
void postorder(struct tree *leaf) {
	if(leaf == NULL)
		return;
	preorder(leaf->left);
	preorder(leaf->right);
	printf("%d\n",leaf->data);									
}

/* Function for delete node from the Tree */
struct tree* delete(struct tree *leaf, int key) {
	if(leaf == NULL)
		printf("Element Not Found!\n");
	else if(key < leaf->data)
		leaf->left = delete(leaf->left, key);
	else if(key > leaf->data)
		leaf->right = delete(leaf->right, key);
	else {
		if(leaf->right && leaf->left) {

			/* Replace with minimum element in the right sub tree */
			temp = minvalue(leaf->right);
			leaf->data = temp->data;

			/* Delete that node */
			leaf->right = delete(leaf->right,temp->data);
		}	
		else {
			/* If there is only one or zero children then directly remove it from the tree and connect its parent to its child */
			temp = leaf;
			if(leaf->left == NULL) 
				leaf = leaf->right;
			else if(leaf->right == NULL)
				leaf = leaf->left;
			free(temp);
			printf("Data delete successfully!\n");
		}
	}									
}

int main() {
	int key, choice;
	while(choice != 7) {
		printf("1. Insert\n2. Search\n3. Delete\n4. Display\n5. Min Value\n6. Max Value\n7. Exit\n");
		printf("Enter your choice:\n");
		scanf("%d", &choice);
		switch(choice) {
			case 1:
				printf("\nEnter the value to insert:\n");
				scanf("%d", &key);
				root = insert(key, root);
				break;
			case 2:
				printf("\nEnter the value to search:\n");
				scanf("%d", &key);
				search(key,root);
				break;
			case 3:
				printf("\nEnter the value to delete:\n");
				scanf("%d", &key);
				delete(root,key);
				break;
			case 4:
				printf("Preorder:\n");
				preorder(root);
				printf("Inorder:\n");
				inorder(root);
				printf("Postorder:\n");
				postorder(root);
				break;
			case 5:
				if(minvalue(root) == NULL)
					printf("Tree is empty!\n");
				else
					printf("Minimum value is %d\n", minvalue(root)->data);
				break;
			case 6:
				if(maxvalue(root) == NULL)
					printf("Tree is empty!\n");
				else
					printf("Maximum value is %d\n", maxvalue(root)->data);
				break;
			case 7:
				printf("Bye Bye!\n");
				exit(0);
				break;
			default:
				printf("Invalid choice!\n");
		}
	}
	return 0;
}







/* Output */
1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
1

Enter the value to insert:
5

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
1

Enter the value to insert:
3

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
1

Enter the value to insert:
6

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
1

Enter the value to insert:
2

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
1

Enter the value to insert:
7

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
1

Enter the value to insert:
9

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
2

Enter the value to search:
2

Data found!

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
3

Enter the value to delete:
9

Data delete successfully!

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
4

Preorder:
5
3
2
6
7

Inorder:
2
3
5
6
7

Postorder:
2
3
7
6
5

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
5

Minimum value is 2

1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
6

Maximum value is 7
1. Insert
2. Search
3. Delete
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
7

Bye Bye!

Comments (0)

  • To add your comment please or

We use cookies to improve your experience on our site and to show you personalised advertising. Please read our cookie policy and privacy policy.

Got It!