Binary Tree

#include<iostream>
using namespace std;

/* Tree structure */
struct tree {
	int data;
	tree *left;
	tree *right;
};

class btree {
	private:
		void destroy_tree(tree *leaf) {
			if(leaf != NULL) {
				destroy_tree(leaf->left);
				destroy_tree(leaf->right);
				delete leaf;
			}
		}

		void insert(int key, tree *leaf) {
			if(key < leaf->data) {
				if(leaf->left != NULL) 
					insert(key, leaf->left);
				else {
					leaf->left = new tree;
					leaf->left->data = key;

					/* Sets the left child of the child node to null */
					leaf->left->left = NULL;

					/* Sets the right child of the child node to null */
					leaf->left->right = NULL;
				}  
			}
			else if(key>=leaf->data) {
				if(leaf->right!=NULL)
					insert(key, leaf->right);
				else {
					leaf->right = new tree;
					leaf->right->data = key;

					/* Sets the left child of the child node to null */
					leaf->right->left = NULL;

					/* Sets the right child of the child node to null */
					leaf->right->right = NULL; 
				}
			}
		}

		tree *search(int key, tree *leaf) {
			if(leaf != NULL) {
				if(key == leaf->data)
					return leaf;
				if(key < leaf->data)
					return search(key, leaf->left);
				else
					return search(key, leaf->right);
			}
			else
				return NULL;
		}

	public:
		tree *root;

		/* Constructor */
		btree() {
			root = NULL;
		}

		/* Destructor */
		~btree() {
			destroy_tree();
		}

		/* Function for Insert data into the Tree */
		void insert(int value) {
			if(root != NULL)
				insert(value, root);
			else {
				root = new tree;
				root->data = value;
				root->left = NULL;
				root->right = NULL;
			}
		}

		/* Function for Search data from the Tree */
		void search(int value) {
			if(search(value, root) == NULL)
				cout << "Not Found!" << endl;
			else
				cout << "Data Found!" << endl;
		}		
	
		/* Function for Destroy Tree */
		void destroy_tree() {
			destroy_tree(root);
		}

		/* Function for find minimum value from the Tree */
		tree *minvalue(struct tree *leaf) {
			if(leaf == NULL)
				return NULL;

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

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

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

		/* Function for print binary tree in Preorder format */
		void preorder(struct tree *leaf) {
			if(leaf == NULL)
				return;
			cout << leaf->data << endl;
			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);
			cout << leaf->data << endl;
			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);
			cout << leaf->data << endl;
		}
};

int main() {
	int key, choice;
	btree bt = btree();
	while(choice != 7) {
		cout << "\n1. Insert\n2. Search\n3. Destroy\n4. Display\n5. Min Value\n6. Max Value\n7. Exit" << endl;
		cout << "Enter your choice:" << endl;
		cin >> choice;
		switch(choice) {
			case 1:
				cout << "Enter the value to insert:" << endl;
				cin >> key;
				bt.insert(key);
				cout << "Data inserted!" << endl;
				break;
			case 2:
				cout << "Enter the value to search:" << endl;
				cin >> key;
				bt.search(key);
				break;
			case 3:
				bt.destroy_tree();
				cout << "Tree Destroyed!" << endl;
				break;
			case 4:
				cout << "Preorder:" << endl;
				bt.preorder(bt.root);
				cout << "Inorder:" << endl;
				bt.inorder(bt.root);
				cout << "Postorder:" << endl;
				bt.postorder(bt.root);
				break;
			case 5:
				if(bt.minvalue(bt.root) == NULL)
					cout << "Tree is empty!" << endl;
				else
					cout << "Minimum value is " << bt.minvalue(bt.root)->data << endl;
				break;
			case 6:
				if(bt.maxvalue(bt.root) == NULL)
					cout << "Tree is empty!" << endl;
				else
					cout << "Maximum value is " << bt.maxvalue(bt.root)->data << endl;
				break;
			case 7:
				cout << "Bye Bye!" << endl;
				return 0;
				break;
			default:
				cout << "Invalid choice!" << endl;
		}
	}
	return 0;
}




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

Enter your choice:
1

Enter the value to insert:
5

Data Inserted!

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

Enter your choice:
1

Enter the value to insert:
3

Data Inserted!

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

Enter your choice:
1

Enter the value to insert:
6

Data Inserted!

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

Enter your choice:
1

Enter the value to insert:
2

Data Inserted!

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

Enter your choice:
1

Enter the value to insert:
7

Data Inserted!

1. Insert
2. Search
3. Destroy
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. Destroy
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. Destroy
4. Display
5. Min Value
6. Max Value
7. Exit

Enter your choice:
5

Minimum value is 2

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

Enter your choice:
6

Maximum value is 7

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

Enter your choice:
3

Tree Destroyed!

1. Insert
2. Search
3. Destroy
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!