Write a function named bstAdd 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 adds that integer value to the tree in the proper place to maintain sorted BST ordering.
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 right place to insert the given value.
Do not add duplicates; if the given value is already 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.
You may construct a new BinaryTreeNode object to attach the new value to the tree, but otherwise do not create or delete any other tree nodes (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;
};
