WE have to add the printTree() method to the BinarySearchTree1 class. As shown b
ID: 3757416 • Letter: W
Question
WE have to add the printTree() method to the BinarySearchTree1 class. As shown below.
public class BinarySearchTreeNode
{
public int key;
public BinarySearchTreeNode left;
public BinarySearchTreeNode right;
}
public class BinarySearchTree1
{
private BinartSearchTreeNode root;
public void insert(int key){}
public void delete(int key){}
public void find(int key){}
Explanation / Answer
package DS;
import java.util.Scanner;
// Class for BinarySearchTreeNode
class BinarySearchTreeNode
{
// To store key value
public int key;
// To point to left child
public BinarySearchTreeNode left;
// To point to right child
public BinarySearchTreeNode right;
// Default constructor to initialize instance variables
public BinarySearchTreeNode(int key)
{
this.key = key;
left = null;
right = null;
key = 0;
}// End of default constructor
}// End of class
// Driver class BinarySearchTree1 definition
public class BinarySearchTree1
{
// Decalares root node
public static BinarySearchTreeNode root;
// Default constructor to initialize root
public BinarySearchTree1()
{
this.root = null;
}// End of default constructor
// Method to returns true if searched element found otherwise returns false
public boolean find(int key)
{
// Declares a current node points to root
BinarySearchTreeNode currentNode = root;
// Initializes found status to false for not found
boolean found = false;
// Traverse till end
while(currentNode != null)
{
// Checks if current key is equal to search data return true
if(currentNode.key == key)
{
// Updates the found status to true
found = true;
// Displays the data
System.out.println("Node found: " + key);
// Come out of the loop
break;
}// End of if condition
// Checks if current data is greater than the search data move left
else if(currentNode.key > key)
currentNode = currentNode.left;
// Otherwise current data is less than the search data move right
else
currentNode = currentNode.right;
}// End of while
// Checks if not found displays message
if(!found)
System.out.println("Node not found: " + key);
// Returns the found status
return found;
}// End of method
// Method to insert key
public void insert(int key)
{
// Creates a node using parameterized constructor
BinarySearchTreeNode newNode = new BinarySearchTreeNode(key);
// Checks if root is null then this node is the first node
if(root == null)
{
// root is pointing to new node
root = newNode;
return;
}// End of if condition
// Otherwise at least one node available
// Declares current node points to root
BinarySearchTreeNode currentNode = root;
// Declares parent node assigns null
BinarySearchTreeNode parentNode = null;
// Loops till node inserted
while(true)
{
// Parent node points to current node
parentNode = currentNode;
// Checks if parameter key is less than the current node key
if(key < currentNode.key)
{
// Current node points to current node left
currentNode = currentNode.left;
// Checks if current node is null
if(currentNode == null)
{
// Parent node left points to new node
parentNode.left = newNode;
return;
}// End of inner if condition
}// End of outer if condition
// Otherwise parameter key is greater than the current node key
else
{
// Current node points to current node right
currentNode = currentNode.right;
// Checks if current node is null
if(currentNode == null)
{
// Parent node right points to new node
parentNode.right = newNode;
return;
}// End of inner if condition
}// End of outer if condition
}// End of while
}// End of method
// Method to call delete() method
void delete(int key)
{
root = delete(root, key);
}
// Method to delete a key node
BinarySearchTreeNode delete(BinarySearchTreeNode root, int key)
{
// Checks if root node is null then tree is empty
if (root == null)
return root;
// Otherwise, checks if parameter key less then root key value
if (key < root.key)
// Recursively calls the method with left child
root.left = delete(root.left, key);
// Otherwise, checks if parameter key greater then root key value
else if (key > root.key)
// Recursively calls the method with right child
root.right = delete(root.right, key);
// Otherwise checks if parameter key is same as root's key
else
{
// Checks if node with only one child or no child
// Checks if left child is null then return right child
if (root.left == null)
return root.right;
// Otherwise checks if right child is null then return left child
else if (root.right == null)
return root.left;
// Situation for node with two children
// Calls the method minValue() to get the in order successor (smallest in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = delete(root.right, root.key);
}// End of else
// Returns the root
return root;
}// End of method
// Method to return smallest key
int minValue(BinarySearchTreeNode root)
{
// Stores the root key as the minimum
int minimum = root.key;
// Loops till left child is not null
while (root.left != null)
{
// Stores the minimum as the current key
minimum = root.left.key;
// Move to next left child
root = root.left;
} // End of while loop
// Returns the minimum
return minimum;
} // End of method
// Tree traversal
void printTree(BinarySearchTreeNode root)
{
// Checks if root is null then empty tree
if (root == null)
return;
// Recursively calls with left child
printTree(root.left);
// Displays the current key value
System.out.print(root.key + " ");
// Recursively calls with right child
printTree(root.right);
}// End of method
// Method to displays menu
void menu()
{
System.out.print(" 1) Insert");
System.out.print(" 2) Delete");
System.out.print(" 3) Find");
System.out.print(" 4) Tree Traversal");
System.out.print(" 5) Exit");
}// End of method
// main method definition
public static void main(String[] ss)
{
// ch - to store choice
// val - to sotre the number entered by the user
int ch, val;
// Scanner class obect created
Scanner sc = new Scanner(System.in);
// Creates an object of the class BinarySearchTree1
BinarySearchTree1 b = new BinarySearchTree1();
System.out.println(" ***************** Binary Search Trees ***************** ");
// Loops till user choice is not 5 entered
do
{
// Calls the method to display menu
b.menu();
// Accepts user choice
System.out.println(" Enter your choice: ");
ch = sc.nextInt();
// Checks user choice
switch(ch)
{
case 1:
// Accepts a number to insert
System.out.println("Enter the key to insert: ");
val = sc.nextInt();
// Calls the method to insert the number
b.insert(val);
break;
case 2:
// Accepts a number to delete
System.out.println("Enter the key to delete: ");
val = sc.nextInt();
// Checks whether the number is available in the tree or not
if(b.find(val))
{
// Calls the method to delete the key
b.delete(val);
System.out.println("Key delete successfully ");
}// End of if condition
break;
case 3:
// Accepts a number to search
System.out.println("Enter the key to find: ");
val = sc.nextInt();
// Calls the method to search the key
b.find(val);
break;
case 4:
// Call the method for tree traversal
if(root == null)
System.out.println("Empty tree.");
b.printTree(root);
break;
case 5:
System.exit(0);
default:
System.out.println("Invalid Choice");
}// End of switch - case
}while(true);// End of while loop
}// End of main
}// End of driver class
Sample Output:
***************** Binary Search Trees *****************
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
9
Invalid Choice
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
4
Empty tree.
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
1
Enter the key to insert:
1
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
1
Enter the key to insert:
2
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
1
Enter the key to insert:
3
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
1
Enter the key to insert:
4
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
1
Enter the key to insert:
5
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
4
1 2 3 4 5
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
3
Enter the key to find:
12
Node not found: 12
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
3
Enter the key to find:
4
Node found: 4
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
2
Enter the key to delete:
45
Node not found: 45
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
2
Enter the key to delete:
3
Node found: 3
Key delete successfully
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
4
1 2 4 5
1) Insert
2) Delete
3) Find
4) Tree Traversal
5) Exit
Enter your choice:
5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.