Binary Tree

import java.io.*;
import java.util.Scanner;

class tree {
	int data;
	tree left;
	tree right;

	tree(int value) {
		this.data = value;
	}
}


class btree {
	tree temp ;

	/* Method for insert data from the Tree */
	void insert(tree node, int value) {
		if (value < node.data) {
			if (node.left != null) 
				insert(node.left, value);
			else {
				System.out.println("Inserted " + value + " to left of "+ node.data);
			        node.left = new tree(value);
			}
		} 
		else if (value > node.data) {
			if (node.right != null) 
				insert(node.right, value);
			else {
				System.out.println("Inserted " + value + " to right of "+ node.data);
			        node.right = new tree(value);
			}
    		}
	}

	/* Method for search data from Tree */
	tree search(int key,tree node) {
		if(node != null) {
			if(key == node.data) {
				System.out.println("Data found!");
				return node;
			}
			else {
				if(key < node.data)
					return search(key,node.left);
				else
					return search(key,node.right);
			}
		}
		else {
			System.out.println("Data not found!");
			return null;
		}
	}

	/* Method for find minimum value from the Tree */
	tree minvalue(tree node) {
		if(node == null)
			return null;

		/* Go to the left sub tree to find the min element */
		if(node.left != null)
			return minvalue(node.left);
		else
			return node;
	}

	/* Method for find maximum value from the Tree */
	tree maxvalue(tree node) {
		if(node == null)
			return null;

		/* Go to the left sub tree to find the max element */
		if(node.right != null)
			return maxvalue(node.right);
		else
			return node;
	}

	/* Method for traversed in preorder from the Tree */
	void preorder(tree node) {
		if (node != null)  {
			System.out.println(node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}

	/* Method for traversed in inorder from the Tree */
	void inorder(tree node) {
		if (node != null) {
			preorder(node.left);
			System.out.println(node.data);
			preorder(node.right);
		}
	}

	/* Method for traversed in postorder from the Tree */
	void postorder(tree node) {
		if (node != null) {
			preorder(node.left);
			preorder(node.right);
			System.out.println(node.data);
		}
	}

	/* Method for delete leaf from the Tree */
	void delete(tree node, int key) {
		if(node == null)
			System.out.println("Element Not Found!");
		else if(key < node.data)
			delete(node.left, key);
		else if(key > node.data)
			delete(node.right, key);
		else {
			if(node.right != null && node.left != null) {

				/* Replace with minimum element in the right sub tree */
				temp = minvalue(node.right);
				node.data = temp.data;

				/* Delete that node */
				delete(node.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 = node;
				if(temp.left == null)
					node.right = temp.right;
				else if(temp.right == null)
					node.left = temp.left;
				temp = null;
				System.out.println("Data delete successfully!\n");
			}
		}
	} 
}


class binarytree {
	public static void main(String args[]) {
		int key, choice = 0;
		Scanner input = new Scanner(System.in);
		tree root = null;
		btree bt = new btree();
		while(choice != 7) {
			System.out.println("1. Insert\n2. Search\n3. Delete\n4. Display\n5. Min Value\n6. Max Value\n7. Exit");
			System.out.println("Enter your choice:");
			choice = Integer.parseInt(input.nextLine());
			switch(choice) {
				case 1:
					System.out.println("Enter the value to insert:");
					if(root == null)
						root = new tree(Integer.parseInt(input.nextLine()));					
					else
						bt.insert(root, Integer.parseInt(input.nextLine()));
					break;
				case 2:
					System.out.println("Enter the value to search:");
					bt.search(Integer.parseInt(input.nextLine()),root);
					break;
				case 3:
					System.out.println("Enter the value to delete:");
					bt.delete(root,Integer.parseInt(input.nextLine()));
					break;
				case 4:
					System.out.println("\nPreorder:");
					bt.preorder(root);
					System.out.println("\nInorder:");
					bt.inorder(root);
					System.out.println("\nPostorder:");
					bt.postorder(root);
					break;
				case 5:
					if(bt.minvalue(root) == null)
						System.out.println("Tree is empty!");
					else
						System.out.println("Minimum value is "+bt.minvalue(root).data);
					break;
				case 6:
					if(bt.maxvalue(root) == null)
						System.out.println("Tree is empty!");
					else
						System.out.println("Maximum value is "+bt.maxvalue(root).data);
					break;
				case 7:
					System.out.println("Bye Bye!");
					System.exit(0);
					break;
				default:
					System.out.println("Invalid choice!");
			}
		}
	}
}




/* 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!