Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

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