public
class
Node {
int
key;
Node left, right, parent;
public
Node() {}
public
Node(int
num) {
key = num;
left =
null;
right =
null;
parent =
null;
}
}
The most important thing is that a node as an object has four attributes: key, left, right, parent. Key holds the value of the node. Left and right refer to the left and right children nodes. Parent refers to the parent node.
Please design a class named BST and include the following attributes/methods:
- Insert: This method accepts one parameter, the target value (an integer), and will add a new node with that value into the Binary Search Tree. This method returns the root of the updated Binary Search Tree.
public Node insert(int target)
- Search: This method accepts one parameter, the target value, and returns a boolean. If the target value is found, this method returns true, otherwise false.
public boolean search(int target)
- Delete: This method accepts one parameter, the target value, and will delete the node with the target value if such a node exists. This method returns the root of the updated Binary Search Tree. You might need to create a set of other supporting methods for the
delete
method.
public Node delete(int target)
The above methods should NOT be declared as static, and you are required to use the given Node class.
import
java.util.*;
class
BST {
// do not change this
private
Node root;
private
ArrayList data;
// DO NOT MODIFY THIS METHOD
public
BST() {
root =
null;
data =
new
ArrayList(0);
}
// DO NOT MODIFY THIS METHOD
public
ArrayList getData() {
return
data;
}
// DO NOT MODIFY THIS METHOD
public
void
inOrderTraversal() {
inOrderTraversal(root);
}
// DO NOT MODIFY THIS METHOD
private
void
inOrderTraversal(Node node) {
if
(node !=
null) {
inOrderTraversal(node.left);
data.add(node.key);
inOrderTraversal(node.right);
}
}
// search
public
boolean
search(int
target) {
// remove this line
return
false;
}
// insert
public
Node insert(int
target) {
// remove this line
return
root;
}
// note: you may need to implement several supporting methods for delete
public
Node delete(int
target) {
// remove this line
return
root;
}
// you are welcome to add any supporting methods
}