Binary Tree

C Programming

C Programming Examples

#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!

Learn more about Binary Tree