class TNode {
public: // a very open class...

  int data;  // int to keep life simple
  // . . .  other data could be added here if desired
  TNode *left, *right;

  TNode (int data, TNode *left, TNode *right) {
    TNode::data = data; TNode::left = left; TNode::right = right;
  }

};


class Tree {
private:

TNode *root;  // root pointer

// make assignment and initialization impossible by declaring these
// operations to be private (i.e. you cannot use these two methods)
Tree (const Tree &otherTree);
Tree &operator= (const Tree &otherTree);

// deletes all of the nodes in a specified subtree
void purge (TNode* subroot);

// search a subtree for a value
bool subSearch (TNode *subroot, int data) const;

// outputs subtree values to "cout", one per line, in order
void subPrint (TNode *subroot) const;

// displays a subtree graphically using specified prefix strings
void subDisplay (String2002 leftPreString, String2002 midPreString,
                 String2002 rightPreString, TNode *subRoot) const;

// deletes the rightmost node in a subtree and returns the value that
// was in this node.  throws an "invalid_argument" exception if given an
// empty tree.
int removeRightmost (TNode* &subroot);

// recursive remove sub method
bool subRemove (TNode* &subroot, int data);

// recursive getHeight sub method
int subGetHeight (TNode *subroot) const;

// recursive sub method to return the number of nodes with right children containing even values.
int subCountNodesWEvenRight(TNode *subroot) const;

// recursive sub method to delete all the nodes in the tree containing odd values.
void subDeleteOddValues(TNode *&subroot);

public:

// default constructor creates empty tree
Tree () { root = NULL; }

~Tree();  // destructor

// returns true if value exists and false otherwise.
bool search (int data) const;

// returns true if insertion successful (data does not already exist)
// and false otherwise.
bool insert (int data);

// returns true if deletion successful (data existed in tree)
// and false otherwise.
bool remove (int data);

// outputs tree values to "cout", one value per line, in order
void print () const;

// outputs tree graphically to "cout"
void display () const;

// returns the height of the tree
int getHeight () const;

// countNodesWEvenRight() returns the number of nodes with right children containing even values.
int countNodesWEvenRight() const;

// findSmallest() returns the smallest value in the tree. Throws overflow_error exception if tree is empty.
int findSmallest() const;

// deleteOddValues() deletes all the nodes in the tree containing odd values.
void deleteOddValues();

};