Binary Search Tree in C++

Syntactic specifications for the C++ implementation of a Binary Search Tree with re-balancing.

Defined struct for a binary tree node (note that the data field is used as the key):

struct BTNode {
    int data;
    BTNode * left;
    BTNode * right;
}

Functions:

Note that these are function signature specifications only and are not to be used as specifications of the required behaviors. Required functionality is provided during in-class sessions. For the following functions, the parameter root is a pointer to the root of the tree to be examined or modified. If the tree is to be modified, the tree must be modified in place and a pointer to the root of the modified tree should be returned.

bool isEmpty(BTNode * root); // Return true if an empty tree
bool isBST(BTNode * root); // Return true if tree is a binary search tree
int height(BTNode * root); // Return the height the tree; 0 for empty tree, 1 for leaf 
int size(BTNode * root); // Return the number of nodes in the tree
BTNode * find(BTNode * root, int data); // Return node that contains data, if any
BTNode * add(BTNode * root, int data); // Return root of tree with data added
BTNode * remove(BTNode * root, int data); // Return root of tree with data removed
int * inorder(BTNode * root); // Return array of data values resulting from inorder traversal
bool isBalanced(BTNode * root); // Return true if tree is balanced
BTNode * balance(BTNode * root); // Return root of rebalanced tree
BTNode * treeToVine(BTNode * root); // Perform treeToVine algorithm
BTNode * vineToTree(BTNode * root); // Perform vineToTree algorithm
BTNode * compress(BTNode * root, int count); // Perform compression algorithm
int main(); // Demonstrate correct behavior of the other functions