//Complete the remove method for a Binary Search Tree in java public class Binar
ID: 3717332 • Letter: #
Question
//Complete the remove method for a Binary Search Tree in java
public class BinarySearchTree {
Node root;
public BinarySearchTree() {
root = null;
}
/*
* Adds the specified node to the BST
*/
public String add(String value) {
if(root == null) {
root = new Node(value);
return value;
}
return add(root, value);
}
private String add(Node root, String value) {
int comp = value.compareTo(root.data);
if(comp == 0)
return value;
if(comp < 0) {
if(root.left != null)
return add(root.left, value);
root.left = new Node(value);
return value;
}
if(comp > 0) {
if(root.right != null)
return add(root.right, value);
root.right = new Node(value);
return value;
}
return null;
}
/*
* Returns true if the string is found in the BST
*/
public boolean find(String value) {
return find(root, value);
}
private boolean find(Node root, String value) {
if(root == null)
return false;
int comp = value.compareTo(root.data);
if(comp == 0)
return true;
if(comp < 0)
return find(root.left, value);
return find(root.right, value);
}
/*
* Checks whether the tree is empty or not
*/
public boolean isEmpty() {
return root == null;
}
/*
* Removes the specified string from the BST
*/
public boolean remove(String s) {
return false;
// To do
}
public boolean remove(Node root, String s) {
return false;
}
// Removes the largest node in the given tree,
// which will be the rightmost node, and returns
// the value from that node. The largest node
// will always have 0 or 1 children (if it had
// 2 children, then the right node would be larger).
private String removeLargestFromLeftSubtree(Node n) {
return null;
// To do, optional, you can accomplish the same task in the remove method. In that case you don't
// have to define this method.
}
/**
* Prints the inorder traversal of this tree
*/
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node root) {
if(root == null)
return;
inorderTraversal(root.left);
System.out.print(root.data + " ");
inorderTraversal(root.right);
}
private class Node{
String data;
Node left;
Node right;
public Node(String data) {
this.data = data;
}
}
/*
* Returns the height of the tree
*/
public int getHeight() {
return getHeight(root);
}
private int getHeight(Node root) {
if(root == null)
return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
Explanation / Answer
Please find the code down.
public boolean remove(String s)(Node root, String S)
{
if (root == null) return root;
if (S < root.data)
root.left =remove(root.left, S);
else if (key > root.key)
root.right =remove(root.right, S);
else
{
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = MinimumValue(root.right);
root.right = remove(root.right, S);
}
return root;
}
Thanks. feel free to ask if something.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.