Binary Search Trees 1. Insert 2. Delete 3. Find Max 4. Find Min 5. Contains 6. I
ID: 3797412 • Letter: B
Question
Binary Search Trees
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. In order Tree Traversal
7. Height
8. No Of Nodes
Your Option: 1
Enter element: 11
Element inserted
Implement binary search tree class with lazy deletion that has TreeNode as nested class in Java. Design the class, TreeNode to have following class variables: int key All keys are in the range 1 to 99 TreeNode left Child; TreeNode right Child; boolean deleted; Your program method must have routines to do the following operations. insert //Should insert a new element to a leaf node. If new element is a duplicate then do nothing. If the new element is previously deleted one, then do not add other copy just mark the previous deleted as valid now delete //should not remove the element from the tree. It should just mark the element as deleted. findMin //Should return the minimum element, but if it is marked deleted return appropriate minimum find Max //should return the maximum element, but if it is marked deleted return appropriate maximum contains //Should return true ifa particular element is in the tree and is not marked as deleted n order tree Traversal //Should print the inorder traversal of the tree. Indicating with symbol for elements that are marked deleted Height returns the height of the tree) //Return the height of the tree, count all the elements even the ones that are marked as deleted No Of nodes returns number of nodes number of deleted nodes) //Print size of the tree, count all the elements even the ones that are marked as deleted. And also return the number of deleted elements. You may have other routines that may be necessary. The program should prompt user with options to do one of the above routines.Explanation / Answer
package myProject;
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)
{
MyNODE parent = root;
MyNODE current = root;
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;
int mark;
MyNODE left;
MyNODE right;
//Constructor
public MyNODE(int key)
{
this.key = key;
left = null;
right = null;
key = 0;
}//end of constructor
}//end of class
Output
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:
11
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:
1
Enter the value to insert:
44
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 = 44
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 = 11
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:
45
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:
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:
6
11 22 33 44
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 = 4
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 = 4
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
11 33 44
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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.