Write a function to find the minimum and maximum nodes within a BST and then rep

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

void deleteTree(TreeNode *node)
{
if (node == NULL)
return

//now onto the recursion
deleteTree(node->leftChild);
deleteTree(node->rightChild);

free(node)
}

void replaceMaxWithMin(TreeNode *root)
{
TreeNode* max = findMaxNode(root);
TreeNode* min = findMinNode(root);
TreeNode *tmp = max;
max->parent->rightChild = min;
min->parent = max->parent;
  
deleteTree(max);
  
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.