Java Programming: Please, implement the next methods in the following code: Note
ID: 3573582 • Letter: J
Question
Java Programming:
Please, implement the next methods in the following code:
Note: The code below is a BST package of data structures and functions that contains implementation of the following operations on BSTs: inorder/preorder/postorder walk, search, maximum, minimum, predecessor, successor, insert and delete.
Sub-BST: Write a method/function that decides whether a given BST is a sub-BST of another BST. Note that a BST t1 is a sub-BST of t2 iff one of the following holds:
key[root[t1]] = key[root[t2]], and left[t1] and right[t1] are sub-BSTs of left[t2] and right[t2], respectively,
t1 is a sub-BST of left[t2], or
t1 is a sub-BST of right[t2].
Note also that an empty BST (root=nil) is a subBST of any BST.
Difference of Pairs on a BST: Write a method/function that outputs two pointers pointing to two nodes, xand y, in a given BST, where the key values of x and y differ by a given integer k. Recall that we had given the following algorithm that on an sorted input array A and given value k returns two indices i and j, where A[i] – A[j] = k, or report error if such i and j do not exist:
i1; j2;
nlength[A] //assuming indices of A start with 1
while (jn and in)
d A[i] – A[j]
if (d==k)
return (i, j)
if (d<k)
i++
else
j++
return (-1, -1) //To indicate no such i and j exists.
Now you just need to adapt the above algorithm to work on a BST and return two (references/pointers of) nodes (not just the values) in the BST with the desired property. Since the above algorithm runs in O(n)time on an sorted array of n elements, the algorithm entailed by your method/function should also run in O(n) time.
_________________________________________________________
Code:
class BSTNode {
private String key;
private BSTNode parent;
private BSTNode leftChild;
private BSTNode rightChild;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public BSTNode getParent() {
return parent;
}
public void setParent(BSTNode parent) {
this.parent = parent;
}
public BSTNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BSTNode leftChild) {
this.leftChild = leftChild;
}
public BSTNode getRightChild() {
return rightChild;
}
public void setRightChild(BSTNode rightChild) {
this.rightChild = rightChild;
}
}
// this class provides the API for a Binary Search Tree implementation
class BSTree {
private BSTNode root; // this field refers to the root node of the Binary Search Tree
// this is the constructor for the Binary Search Tree class
public BSTree() { this.root = null; }
public void setRoot(BSTNode root) { this.root = root; }
public BSTNode getRoot() { return this.root; }
// this method does the inorder tree walk on the binary search tree
public void inorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
inorderTreeWalk(node.getLeftChild());
System.out.print(node.getKey() + " ");
inorderTreeWalk(node.getRightChild());
}
// this method does the pre-order tree walk on the binary search tree
public void preorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
System.out.print(node.getKey() + " ");
preorderTreeWalk(node.getLeftChild());
preorderTreeWalk(node.getRightChild());
}
// this method does the post-order tree walk on the binary search tree
public void postorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
postorderTreeWalk(node.getLeftChild());
postorderTreeWalk(node.getRightChild());
System.out.print(node.getKey() + " ");
}
// this method finds the node with the minimum key value in the Binary Search Tree
public BSTNode findMinimum() {
BSTNode temp = this.root;
while(temp.getLeftChild() != null) {
temp = temp.getLeftChild();
}
return temp;
}
// this method finds the node with the maximum key value in the Binary Search Tree
public BSTNode findMaximum() {
BSTNode temp = this.root;
while (temp.getRightChild() != null) {
temp = temp.getRightChild();
}
return temp;
}
// this method is used to search the Binary Search Tree for a node with the value passed in the parameter
public BSTNode searchNode(String key) {
BSTNode temp = this.root;
while(temp != null && !temp.getKey().equals(key)) {
if(key.compareTo(temp.getKey()) <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
return temp;
}
// this is a private method that is useful in finding the successor of a node passed to the method
private BSTNode helpFindSuccessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getLeftChild() != null) {
node = node.getLeftChild();
}
return node;
}
// this method is used to find the successor node of the node with the given input key
public BSTNode getSuccessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getRightChild() != null) {
return helpFindSuccessor(node.getRightChild());
}
BSTNode successorNode = node.getParent();
while(successorNode != null && successorNode.getLeftChild() != node) {
node = successorNode;
successorNode = successorNode.getParent();
}
return successorNode;
}
// this private method helps us in find the predecessor node in the left subtree of a binary search tree
private BSTNode helpFindPredecessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getRightChild() != null) {
node = node.getRightChild();
}
return node;
}
// this method is used to find the predecessor node of the node with the given input key
public BSTNode getPredecessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getLeftChild() != null) {
return helpFindPredecessor(node.getLeftChild());
}
BSTNode predecessorNode = node.getParent();
while(predecessorNode != null && node != predecessorNode.getRightChild()) {
node = predecessorNode;
predecessorNode = predecessorNode.getParent();
}
return predecessorNode;
}
// this method inserts a node with a given value in the Binary Search Tree
public void insertNode(String value) {
// allocate a new node object for the key that needs to be inserted in the Binary Search Tree
BSTNode node = new BSTNode();
node.setKey(value);
node.setParent(null);
node.setLeftChild(null);
node.setRightChild(null);
// if the Binary Search Tree is initially empty then we make the new node to be the root of the Binary Search Tree
if(this.root == null) {
this.root = node;
} else {
BSTNode parentNode = null;
BSTNode temp = this.root;
while(temp != null) {
parentNode = temp;
int compareValue = node.getKey().compareTo(temp.getKey());
if(compareValue <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
// set the new node's parent to be the parentNode object that was set in the loop
node.setParent(parentNode);
if(node.getKey().compareTo(parentNode.getKey()) <= 0) {
parentNode.setLeftChild(node);
} else {
parentNode.setRightChild(node);
}
}
}
// this method is used to delete a node from the Binary Search Tree
public void deleteNode(BSTNode node) {
// check if the node to be deleted is a valid reference, if its an invalid reference then we don't need to do anything at all
if(node == null) {
return;
}
// Case-1 : If the node to be deleted has no child references at all
if(node.getLeftChild() == null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node
if(parentNode == null) {
this.root = null;
} else if (parentNode.getLeftChild() == node) {
parentNode.setLeftChild(null );
} else {
parentNode.setRightChild(null);
}
node.setParent(null);
}
// Case-2 : If the node to be deleted has one node as its child node
if(node.getLeftChild() != null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a left child then make the left child of the root node as root
if(parentNode == null) {
this.root = node.getLeftChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getLeftChild());
} else {
parentNode.setRightChild(node.getLeftChild());
}
}
node.getLeftChild().setParent(parentNode);
node.setParent(null);
node.setLeftChild(null);
}
if(node.getLeftChild() == null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a right child
if(parentNode == null) {
this.root = node.getRightChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getRightChild());
} else {
parentNode.setRightChild(node.getRightChild());
}
}
node.getRightChild().setParent(parentNode);
node.setParent(null);
node.setRightChild(null);
}
// Case-3 : if the node to be deleted has both a left and a right child
if(node.getLeftChild() != null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// first we get the successor of the node in the Binary Search Tree
BSTNode successorNode = getSuccessor(node.getKey());
BSTNode successorParent = successorNode.getParent();
BSTNode successorRightChild = successorNode.getRightChild();
// if the successor node doesn't have any right child, it obviously doesn't have any left child as its the successor node
if(successorRightChild == null) {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(null);
} else {
successorParent.setLeftChild(null);
}
return;
} else {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(successorRightChild);
} else {
successorParent.setLeftChild(successorRightChild);
}
}
successorRightChild.setParent(successorParent);
successorNode.setParent(null);
successorNode.setLeftChild(null);
successorNode.setRightChild(null);
}
}
}
public class BinarySearchTree {
public static void main(String[] args) {
BSTree tree = new BSTree();
tree.insertNode("D");
tree.insertNode("B");
tree.insertNode("C");
tree.insertNode("A");
tree.insertNode("F");
tree.insertNode("G");
// tree.insertNode("E");
tree.insertNode("I");
tree.insertNode("H");
tree.insertNode("J");
tree.insertNode("L");
tree.insertNode("K");
System.out.println("Inorder Tree Walk : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Preorder Tree Walk : ");
tree.preorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Postorder Tree Walk : ");
tree.postorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Node with the minimum key in the Binary Search Tree : " + tree.findMinimum().getKey());
System.out.println("Node with the maximum key in the Binary Search Tree : " + tree.findMaximum().getKey());
tree.deleteNode(tree.searchNode("D"));
System.out.println("Inorder Tree Walk after deletion of node D : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
}
}
Explanation / Answer
Please refer to comment for details:
add three methods differenceOfPairs, isSubtree, areIdentical here areIdentical method is supporting method of isSubtree. Again refer to comments.
Program:
class BSTNode {
private String key;
private BSTNode parent;
private BSTNode leftChild;
private BSTNode rightChild;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public BSTNode getParent() {
return parent;
}
public void setParent(BSTNode parent) {
this.parent = parent;
}
public BSTNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BSTNode leftChild) {
this.leftChild = leftChild;
}
public BSTNode getRightChild() {
return rightChild;
}
public void setRightChild(BSTNode rightChild) {
this.rightChild = rightChild;
}
}
// this class provides the API for a Binary Search Tree implementation
class BSTree {
private BSTNode root; // this field refers to the root node of the Binary Search Tree
// this is the constructor for the Binary Search Tree class
public BSTree() { this.root = null; }
public void setRoot(BSTNode root) { this.root = root; }
public BSTNode getRoot() { return this.root; }
// this method does the inorder tree walk on the binary search tree
public void inorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
inorderTreeWalk(node.getLeftChild());
System.out.print(node.getKey() + " ");
inorderTreeWalk(node.getRightChild());
}
// this method does the pre-order tree walk on the binary search tree
public void preorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
System.out.print(node.getKey() + " ");
preorderTreeWalk(node.getLeftChild());
preorderTreeWalk(node.getRightChild());
}
// this method does the post-order tree walk on the binary search tree
public void postorderTreeWalk(BSTNode node) {
if(node == null) {
return;
}
postorderTreeWalk(node.getLeftChild());
postorderTreeWalk(node.getRightChild());
System.out.print(node.getKey() + " ");
}
// this method checks if two tree are equal or not
public boolean areIdentical(BSTNode root1, BSTNode root2)
{
/* base cases */
if (root1 == null && root2 == null)
return true;
if (root1 == null || root2 == null)
return false;
/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1.getKey() == root2.getKey() &&
areIdentical(root1.getLeftChild(), root2.getLeftChild()) &&
areIdentical(root1.getRightChild(), root2.getRightChild()) );
}
//this method finds the tree node2 is subtree of tree node1 or not
public boolean isSubtree(BSTNode node1, BSTNode node2){
if (node2 == null)
return true;
if (node1 == null)
return false;
/* Check the tree with root as current node */
if (areIdentical(node1, node2))
return true;
/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(node1.getLeftChild(), node2) ||
isSubtree(node1.getRightChild(), node2);
}
// this method print two nodes whose value's differ by k units
public void differenceOfPairs(BSTree node, int k){
if (node == null){
return;
}
BSTNode beginingNode = node.findMinimum();
BSTNode nextBeginingNode = getSuccessor(beginingNode.getKey());
while(beginingNode != null && (nextBeginingNode != null)){
int d = nextBeginingNode.getKey().length() - beginingNode.getKey().length(); // no diff logic defined so Taking distance as difference in length of strings
if (d == k){
System.out.println("Distance between" + nextBeginingNode.getKey() + " and " + beginingNode.getKey() + " = " + k);
return;
}
if (d < k){
beginingNode = getSuccessor(beginingNode.getKey());
}else{
nextBeginingNode = getSuccessor(nextBeginingNode.getKey());
}
}
System.out.println("No node values differ by k units.");
}
// this method finds the node with the minimum key value in the Binary Search Tree
public BSTNode findMinimum() {
BSTNode temp = this.root;
while(temp.getLeftChild() != null) {
temp = temp.getLeftChild();
}
return temp;
}
// this method finds the node with the maximum key value in the Binary Search Tree
public BSTNode findMaximum() {
BSTNode temp = this.root;
while (temp.getRightChild() != null) {
temp = temp.getRightChild();
}
return temp;
}
// this method is used to search the Binary Search Tree for a node with the value passed in the parameter
public BSTNode searchNode(String key) {
BSTNode temp = this.root;
while(temp != null && !temp.getKey().equals(key)) {
if(key.compareTo(temp.getKey()) <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
return temp;
}
// this is a private method that is useful in finding the successor of a node passed to the method
private BSTNode helpFindSuccessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getLeftChild() != null) {
node = node.getLeftChild();
}
return node;
}
// this method is used to find the successor node of the node with the given input key
public BSTNode getSuccessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getRightChild() != null) {
return helpFindSuccessor(node.getRightChild());
}
BSTNode successorNode = node.getParent();
while(successorNode != null && successorNode.getLeftChild() != node) {
node = successorNode;
successorNode = successorNode.getParent();
}
return successorNode;
}
// this private method helps us in find the predecessor node in the left subtree of a binary search tree
private BSTNode helpFindPredecessor(BSTNode node) {
if(node == null) {
return null;
}
while(node.getRightChild() != null) {
node = node.getRightChild();
}
return node;
}
// this method is used to find the predecessor node of the node with the given input key
public BSTNode getPredecessor(String key) {
BSTNode node = searchNode(key);
if(node == null) {
return null;
}
if(node.getLeftChild() != null) {
return helpFindPredecessor(node.getLeftChild());
}
BSTNode predecessorNode = node.getParent();
while(predecessorNode != null && node != predecessorNode.getRightChild()) {
node = predecessorNode;
predecessorNode = predecessorNode.getParent();
}
return predecessorNode;
}
// this method inserts a node with a given value in the Binary Search Tree
public void insertNode(String value) {
// allocate a new node object for the key that needs to be inserted in the Binary Search Tree
BSTNode node = new BSTNode();
node.setKey(value);
node.setParent(null);
node.setLeftChild(null);
node.setRightChild(null);
// if the Binary Search Tree is initially empty then we make the new node to be the root of the Binary Search Tree
if(this.root == null) {
this.root = node;
} else {
BSTNode parentNode = null;
BSTNode temp = this.root;
while(temp != null) {
parentNode = temp;
int compareValue = node.getKey().compareTo(temp.getKey());
if(compareValue <= 0) {
temp = temp.getLeftChild();
} else {
temp = temp.getRightChild();
}
}
// set the new node's parent to be the parentNode object that was set in the loop
node.setParent(parentNode);
if(node.getKey().compareTo(parentNode.getKey()) <= 0) {
parentNode.setLeftChild(node);
} else {
parentNode.setRightChild(node);
}
}
}
// this method is used to delete a node from the Binary Search Tree
public void deleteNode(BSTNode node) {
// check if the node to be deleted is a valid reference, if its an invalid reference then we don't need to do anything at all
if(node == null) {
return;
}
// Case-1 : If the node to be deleted has no child references at all
if(node.getLeftChild() == null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node
if(parentNode == null) {
this.root = null;
} else if (parentNode.getLeftChild() == node) {
parentNode.setLeftChild(null );
} else {
parentNode.setRightChild(null);
}
node.setParent(null);
}
// Case-2 : If the node to be deleted has one node as its child node
if(node.getLeftChild() != null && node.getRightChild() == null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a left child then make the left child of the root node as root
if(parentNode == null) {
this.root = node.getLeftChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getLeftChild());
} else {
parentNode.setRightChild(node.getLeftChild());
}
}
node.getLeftChild().setParent(parentNode);
node.setParent(null);
node.setLeftChild(null);
}
if(node.getLeftChild() == null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// if the node to be deleted is the root node and it has a right child
if(parentNode == null) {
this.root = node.getRightChild();
} else {
// if the node to be deleted is the left child of its parent node
if(parentNode.getLeftChild() == node) {
parentNode.setLeftChild(node.getRightChild());
} else {
parentNode.setRightChild(node.getRightChild());
}
}
node.getRightChild().setParent(parentNode);
node.setParent(null);
node.setRightChild(null);
}
// Case-3 : if the node to be deleted has both a left and a right child
if(node.getLeftChild() != null && node.getRightChild() != null) {
BSTNode parentNode = node.getParent();
// first we get the successor of the node in the Binary Search Tree
BSTNode successorNode = getSuccessor(node.getKey());
BSTNode successorParent = successorNode.getParent();
BSTNode successorRightChild = successorNode.getRightChild();
// if the successor node doesn't have any right child, it obviously doesn't have any left child as its the successor node
if(successorRightChild == null) {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(null);
} else {
successorParent.setLeftChild(null);
}
return;
} else {
node.setKey(successorNode.getKey());
if(successorParent.getRightChild() == successorNode) {
successorParent.setRightChild(successorRightChild);
} else {
successorParent.setLeftChild(successorRightChild);
}
}
successorRightChild.setParent(successorParent);
successorNode.setParent(null);
successorNode.setLeftChild(null);
successorNode.setRightChild(null);
}
}
}
public class BinarySearchTree {
public static void main(String[] args) {
BSTree tree = new BSTree();
tree.insertNode("D");
tree.insertNode("B");
tree.insertNode("C");
tree.insertNode("A");
tree.insertNode("F");
tree.insertNode("G");
// tree.insertNode("E");
tree.insertNode("I");
tree.insertNode("H");
tree.insertNode("J");
tree.insertNode("L");
tree.insertNode("K");
System.out.println("Inorder Tree Walk : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Preorder Tree Walk : ");
tree.preorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Postorder Tree Walk : ");
tree.postorderTreeWalk(tree.getRoot());
System.out.println();
System.out.println("Two Tree Node with k distance away: ");
tree.differenceOfPairs(tree, 0);
System.out.println();
System.out.println("Checking subtree: ");
boolean subtree = tree.isSubtree(tree.getRoot(), tree.findMinimum());
if (subtree){
System.out.println(tree.findMinimum().getKey() + "is sub tree of " + tree.getRoot().getKey());
}else{
System.out.println(tree.findMinimum().getKey() + "is not sub tree of " + tree.getRoot().getKey());
}
System.out.println();
System.out.println("Node with the minimum key in the Binary Search Tree : " + tree.findMinimum().getKey());
System.out.println("Node with the maximum key in the Binary Search Tree : " + tree.findMaximum().getKey());
tree.deleteNode(tree.searchNode("D"));
System.out.println("Inorder Tree Walk after deletion of node D : ");
tree.inorderTreeWalk(tree.getRoot());
System.out.println();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.