Write a function named bstRemove that accepts a reference to a pointer to a BinaryTreeNode representing the root of a binary search tree of integers, along with an integer value, and removes that integer value from the tree while maintaining sorted BST ordering.
If the node to remove has two non-null children, you should replace it with the minimum element from its right subtree.
You may assume that the tree passed is in BST order, meaning that every node N's left subtree is a BST that contains only values less than N's data, and its right subtree is a BST that contains only values greater than N's data.
Your code should take advantage of the tree's ordering and should not examine any subtrees where there is no possibility of finding the given value.
If the given value is not present in the tree, your function should not modify the tree's state.
Note that the tree node pointer passed to your function should be passed by reference so that you can modify its state directly if necessary.
Constraints:
You must implement your function recursively and without using loops.
Do not construct any new BinaryTreeNode objects in solving this problem (though you may create as many BinaryTreeNode* pointer variables as you like).
Do not use any auxiliary data structures to solve this problem (no array, vector, stack, queue, string, etc).
Your function should not modify any other parts of the tree other than the addition of the new element; the other elements and their relative placement and ordering should not be modified by your function.
Assume that you are using the BinaryTreeNode structure as defined below:
struct BinaryTreeNode {
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
};
