Need help in java Binary Search Trees with Lazy Deletion Implement binary search

Question

Need help in java

Binary Search Trees with Lazy Deletion 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 leftChild TreeNode rightChild; 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 findMax //Should return the maximum element, but if it is marked deleted return appropriate maximum contains //Should return true if a particular element is in the tree and is not marked as deleted In order tree Traversal //Should print the in order 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

Explanation / Answer

Given below is the program with output . Please don't forget to rate the answer if it helped. Thank you.

To indent the code, in a file press Ctrl + A and then Ctrl + i in eclipse.

BST.java

public class BST
{
class TreeNode
{
int key;
TreeNode leftChild;
TreeNode rightChild;
boolean deleted;
TreeNode(int k)
{
key = k;
leftChild = null;
rightChild = null;
deleted = false;
}
}
private TreeNode root;
public boolean insert(int key)
{
TreeNode n = new TreeNode(key);
if(root == null)
{
root = n;
return true;
}
else
{
TreeNode curr = root;
while(curr != null)
{
if(key == curr.key)
{
if(curr.deleted)
{
curr.deleted = false;
return true;
}
else
return false;//duplicate , don't insert
}
else if(key < curr.key)
{
if(curr.leftChild == null)
{
curr.leftChild = n;
return true;
}
else
curr = curr.leftChild;
}
else
{
if(curr.rightChild == null)
{
curr.rightChild = n;
return true;
}
else
curr = curr.rightChild;
}
}
return false;
}

}
public boolean delete(int key)
{
TreeNode curr = root;
while(curr != null)
{
if(key == curr.key)
{
if(!curr.deleted)
{
curr.deleted = true;
return true;
}
else
return false;
}
else if(key < curr.key)
{
curr = curr.leftChild;
}
else
{
curr = curr.rightChild;
}
}
return false;
}
//returns 0 when tree is empty
public int findMin()
{
if(root == null)
return 0;
TreeNode curr = root;
int currentMin = 0;
while(curr != null)
{
if(!curr.deleted)
currentMin = curr.key;
curr = curr.leftChild;
}
return currentMin;
}
//returns 0 when tree is empty
public int findMax()
{
if(root == null)
return 0;
TreeNode curr = root;
int currentMax = 0;
while(curr != null)
{
if(!curr.deleted)
currentMax = curr.key;
curr = curr.rightChild;
}
return currentMax;
}
boolean contains(int key)
{
TreeNode curr = root;
while(curr != null)
{
if(key == curr.key)
{
if(!curr.deleted)
return true;
else
return false;
}
else if(key < curr.key)
{
curr = curr.leftChild;
}
else
{
curr = curr.rightChild;
}
}
return false;
}
private void inorder(TreeNode n)
{
if(n == null) return;
inorder(n.leftChild);
if(n.deleted)
System.out.print("*");
System.out.print(n.key + " ");
inorder(n.rightChild);
}
public void inorder()
{
System.out.println("Inorder traversal:");
inorder(root);
System.out.println();
}
//height is the no. of edges in the longes path
private int height(TreeNode n)
{
//when no node or node with no children, height is 0
if(n == null || (n.leftChild == null && n.rightChild == null))
return 0;
else if(n.leftChild == null && n.rightChild != null)
return 1 + height(n.rightChild);
else if(n.leftChild != null && n.rightChild == null)
return 1 + height(n.leftChild);
else
{
int lh = height(n.leftChild);
int rh = height(n.rightChild);
if(lh > rh)
return 1 + lh;
else
return 1 + rh;
}
}
public int height()
{
return height(root);
}
private int noOfNodes(TreeNode n)
{
int count = 0;
if(n != null)
{
count++;
count += noOfNodes(n.leftChild);
count += noOfNodes(n.rightChild);
}
return count;
}
public int noOfNodes()
{
return noOfNodes(root);
}
}

TestBST.java

import java.util.Scanner;
public class TestBST {
public static void main(String[] args) {
Scanner keybd = new Scanner(System.in);
int choice = 0;
int key;
BST bst = new BST();
while(choice != 9)
{
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. Inorder Traversal");
System.out.println("7. Height");
System.out.println("8. No. of Nodes");
System.out.println("9. Exit");
System.out.print("Your option: ");
choice = keybd.nextInt();
switch(choice)
{
case 1:
System.out.print("Enter key to insert: ");
key = keybd.nextInt();
if(bst.insert(key))
System.out.println("Inserted " + key);
else
System.out.println("Duplicate " + key);
break;
case 2:
System.out.print("Enter key to delete: ");
key = keybd.nextInt();
if(bst.delete(key))
System.out.println("Deleted " + key);
else
System.out.println("Not existing " + key);
break;
case 3:
System.out.println("Max = " + bst.findMax());
break;
case 4:
System.out.println("Min = " + bst.findMin());
break;
case 5:
System.out.print("Enter key to search: ");
key = keybd.nextInt();
if(bst.contains(key))
System.out.println("Found " + key);
else
System.out.println("Not existing " + key);
break;
case 6:
bst.inorder();
break;
case 7:
System.out.println("Height = " + bst.height());
break;
case 8:
System.out.println("No. of nodes = " + bst.noOfNodes());
break;
case 9:
break;
default:
System.out.println("Invalid menu choice!");
}
}
}
}

output

1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 1
Enter key to insert: 5
Inserted 5
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 1
Enter key to insert: 3
Inserted 3
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 1
Enter key to insert: 9
Inserted 9
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 1
Enter key to insert: 10
Inserted 10
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 3
Max = 10
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 4
Min = 3
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 5
Enter key to search: 2
Not existing 2
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 5
Enter key to search:
5
Found 5
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 6
Inorder traversal:
3 5 9 10
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 7
Height = 2
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 8
No. of nodes = 4
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 2
Enter key to delete: 2
Not existing 2
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 2
Enter key to delete: 5
Deleted 5
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 6
Inorder traversal:
3 *5 9 10
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 2
Enter key to delete: 5
Not existing 5
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 1
Enter key to insert: 5
Inserted 5
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 6
Inorder traversal:
3 5 9 10
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 5
Enter key to search: 10
Found 10
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 1
Enter key to insert: 5
Duplicate 5
1. Insert
2. Delete
3. Find Max
4. Find Min
5. Contains
6. Inorder Traversal
7. Height
8. No. of Nodes
9. Exit
Your option: 9

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.