Write a function to find the minimum and maximum nodes within a BST and then rep
ID: 3817829 • Letter: W
Question
Write a function to find the minimum and maximum nodes within a BST and then replace the maximum node with the minimum node. Then, delete the minimum node.
You should call the provided functions, findMinNode(node) and findMaxNode(node) to find the minimum node and maximum nodes in the tree; Call these functions within the function you write.
Header: void replaceMaxWithMin(TreeNode *root);
TreeNode struct:
struct TreeNode{
int key;
TreeNode *leftChild;
TreeNode *rightChild;
TreeNode *parent;
};
Functions to call to get the min and max:
TreeNode* findMinNode(TreeNode* min){
while (min->leftChild != NULL){
min = min->leftChild;
}
return min;
}
TreeNode* findMaxNode(TreeNode* max){
while (max->rightChild != NULL){
max = max->rightChild;
}
return max;
}
Explanation / Answer
struct TreeNode{
int key;
TreeNode *leftChild;
TreeNode *rightChild;
TreeNode *parent;
};
TreeNode* findMinNode(TreeNode* min){
while (min->leftChild != NULL){
min = min->leftChild;
}
return min;
}
TreeNode* findMaxNode(TreeNode* max){
while (max->rightChild != NULL){
max = max->rightChild;
}
return max;
}
//method that replaces max with min...and then deletes the min node
void replaceMaxWithMin(TreeNode *root)
{
TreeNode *max = findMaxNode(root);//finds the max node
TreeNode *min = findMinNode(root);//finds the min node
//replacing max with min
max->key=min->key;
//deleting min node...
//min node doesn't have any left childs...because it is bst
//so
//linking right node of min to min's parent
min->parent->left=min->right;
//making min parent as min's right childs parent
min->right->parent=min->parent;
//removing min
free(min);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.