Create a Java class that implements a Binary Search Tree. The class must include
ID: 3861016 • Letter: C
Question
Create a Java class that implements a Binary Search Tree. The class must include the following functions:
height() - provides the height of the binary tree
size() - provides the size of the binary tree
subtree() - finds the first binary subtree (according to the tree pre-ordering) whose root is equal to that of some given object
insert() - insert an object into the tree
find() - find an object in the tree
find_min() - find the least object in the tree
find_max() - find the greatest object in the tree
delete() - delete an object from the tree
Explanation / Answer
package Online;
import java.util.*;
//Class BinarySearchTree
public class BinarySearchTree
{
//Root node
public static MyNODE root;
//Constructor
public BinarySearchTree()
{
this.root = null;
}
//Returns true if searched element found
public boolean find(int id)
{
MyNODE current = root;
//Traverse till end
while(current!=null)
{
//if current key is equal to search data return true
if(current.key==id)
{
return true;
}
//If current data is greater than the search data move left
else if(current.key>id)
{
current = current.left;
}
//If current data is less than the search data move right
else
{
current = current.right;
}
}//end of while
//return false if not found
return false;
}
//Delete a specified data
public boolean delete(int id)
{
//For parent node
MyNODE parent = root;
//For current lone
MyNODE current = root;
//Set the lift child to false
boolean isLeftChild = false;
//Loops till current key value is not equals to data to be deleted
while(current.key != id)
{
parent = current;
//If current data is greater than the search data move left
if(current.key > id)
{
isLeftChild = true;
current = current.left;
}
//If current data is less than the search data move right
else
{
isLeftChild = false;
current = current.right;
}
//If current is null or empty
if(current == null)
{
return false;
}
}//end of while
//Case 1: if node to be deleted has no children
if(current.left == null && current.right == null)
{
if(current == root)
{
root = null;
}
if(isLeftChild == true)
{
parent.left = null;
}
else
{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right == null)
{
if(current == root)
{
root = current.left;
}
else if(isLeftChild)
{
parent.left = current.left;
}
else
{
parent.right = current.left;
}
}
else if(current.left == null)
{
if(current==root)
{
root = current.right;
}
else if(isLeftChild)
{
parent.left = current.right;
}
else
{
parent.right = current.right;
}
}
else if(current.left != null && current.right != null)
{
//now we have found the minimum element in the right sub tree
MyNODE successor = getSuccessor(current);
if(current==root)
{
root = successor;
}
else if(isLeftChild)
{
parent.left = successor;
}
else
{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
//Gets the successor of the deleted node
public MyNODE getSuccessor(MyNODE deleleNode)
{
MyNODE successsor = null;
MyNODE successsorParent =null;
MyNODE current = deleleNode.right;
//Loops till current is null
while(current!=null)
{
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.right)
{
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
//Inseart data
public void insert(int id)
{
MyNODE newNode = new MyNODE(id);
//If empty
if(root==null)
{
root = newNode;
return;
}
MyNODE current = root;
MyNODE parent = null;
while(true)
{
parent = current;
//If inserted element is less than the current data
if(id<current.key)
{
current = current.left;
if(current==null)
{
parent.left = newNode;
return;
}
}
//If inserted element is greater than the current data
else
{
current = current.right;
if(current==null)
{
parent.right = newNode;
return;
}
}//end of else
}//end of while
}//end of method
//Returns number of data
public int countNode(MyNODE node)
{
MyNODE current = node;
int counter = 0;
//If root is not null
if(current != null)
counter++;
//Loops till left is not null increase the counter
while(current.left!= null)
{
counter++;
/* first recur on left child */
current = current.left;
}
current = root;
//Loops till right is not null increase the counter
while(current.right != null)
{
counter++;
/* first recur on right child */
current = current.right;
}
//Returns counter
return counter;
}
// Given a binary tree, print its nodes in inorder
void printInorder(MyNODE node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.key + " ");
/* now recur on right child */
printInorder(node.right);
}
//Return the minimum data value found in tree.
int findMinimum(MyNODE node)
{
MyNODE current = node;
/* loop down to find the leftmost leaf */
while (current.left != null)
{
current = current.left;
}
return (current.key);
}
//Return the minimum data value found in tree.
int findMaximum(MyNODE node)
{
MyNODE current = node;
/* loop down to find the leftmost leaf */
while (current.right != null)
{
current = current.right;
}
return (current.key);
}
/* Compute the "maxDepth" of a tree -- the number of
* nodes along the longest path from the root node
down to the farthest leaf node.*/
int maxDepth(MyNODE node)
{
if (node == null)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node.left);
int rDepth = maxDepth(node.right);
/* use the larger one */
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}
//Displays menu
void menu()
{
System.out.println("1) Insert");
System.out.println("2) Delete");
System.out.println("3) Find Max");
System.out.println("4) Find Min");
System.out.println("5) Contains");
System.out.println("6) In order Tree Traversal");
System.out.println("7) Height");
System.out.println("8) Number of nodes");
System.out.println("9) Exit");
}
//Main method
public static void main(String arg[])
{
int ch, val;
Scanner sc = new Scanner(System.in);
BinarySearchTree b = new BinarySearchTree();
System.out.println("Binary Search Trees");
//Loops till 9 entered
do
{
b.menu();
System.out.println("Enter your choice: ");
ch = sc.nextInt();
switch(ch)
{
case 1:
System.out.println("Enter the value to insert: ");
val = sc.nextInt();
b.insert(val);
break;
case 2:
System.out.println("Enter the value to delete: ");
val = sc.nextInt();
if(b.find(val))
b.delete(val);
break;
case 3:
System.out.println("Maximum = " + b.findMaximum(root));
break;
case 4:
System.out.println("Minimum = " + b.findMinimum(root));
break;
case 5:
System.out.println("Enter the value to Search: ");
val = sc.nextInt();
if(b.find(val))
System.out.println("Found");
else
System.out.println("Not Found");
break;
case 6:
b.printInorder(root);
System.out.println();
break;
case 7:
System.out.println("Maximum depth = " + b.maxDepth(root));
break;
case 8:
System.out.println("Number of Nodes = " + b.countNode(root));
break;
case 9:
System.exit(0);
default:
System.out.println("Invalid Choice");
}
}while(true);
}//end of main
}//End of class
//Class for Node
class MyNODE
{
int key;
boolean deleted;
MyNODE left;
MyNODE right;
//Constructor
public MyNODE(int key)
{
this.key = key;
left = null;
right = null;
key = 0;
}//end of constructor
}//end of class
Sample Run:
Binary Search Trees
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
1
Enter the value to insert:
10
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
1
Enter the value to insert:
22
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
1
Enter the value to insert:
33
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
6
10 22 33
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
1
Enter the value to insert:
5
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
6
5 10 22 33
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
2
Enter the value to delete:
22
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
6
5 10 33
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
3
Maximum = 33
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
4
Minimum = 5
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
5
Enter the value to Search:
88
Not Found
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
6
5 10 33
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
5
Enter the value to Search:
33
Found
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
7
Maximum depth = 2
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
8
Number of Nodes = 3
1) Insert
2) Delete
3) Find Max
4) Find Min
5) Contains
6) In order Tree Traversal
7) Height
8) Number of nodes
9) Exit
Enter your choice:
9