LANGUAGE IN JAVA. Last one I was given did not work. Please make sure it works.
ID: 3773030 • Letter: L
Question
LANGUAGE IN JAVA.
Last one I was given did not work. Please make sure it works.
Implement or adapt a BST class (preferred) or a 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. assume that each node in a BST has at least four fields: key, p, left, and right, representing the key value, and parent, left, and right child nodes of the given node. In addition, key values of all nodes in a BST are assumed to be integers. Write a method/function that outputs two, x and y, in a given BST, where the key values of x and y differ by a given integer k. 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]. Write a method/function that prunes a BST by “deleting” nodes with key values out of a given range [min, max].
Basically Difference of Pairs on a BST, Sub-BST, and Pruning BSTs
Explanation / Answer
node* removeOutsideRange(node *root, int min, int max)
{
// Base Case
if (root == NULL)
return NULL;
// First fix the left and right subtrees of root
root->left = removeOutsideRange(root->left, min, max);
root->right = removeOutsideRange(root->right, min, max);
if (root->key < min)
{
node *rChild = root->right;
delete root;
return rChild;
}
// 1.b) Root's key is greater than max value (root is not in range)
if (root->key > max)
{
node *lChild = root->left;
delete root;
return lChild;
}
return root;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.