Assume class Binary Tree contains a single pointer to the root of the tree. Implement a recursive member function for class BinTree that returns true if the object is a binary search tree and false otherwise. This function will be a private function isBinSearchTree that would be called from a public interface function.

//Stack template

template <class T>

class BinaryTree

{

private:

struct TreeNode

{

T value; //The value in the node

TreeNode *left; //Pointer to left child node

TreeNode *right; //Pointer to right child node

};

TreeNode *root; //Pointer to the root node

//Private member functions

void insert(TreeNode*&, TreeNode *&);

void destroySubTree(TreeNode *);

void deleteNode(T, TreeNode *&);

void makeDeletion(TreeNode *&);

void displayInOrder(TreeNode *) const;

void displayPreOrder(TreeNode *) const;

void displayPostOrder(TreeNode *) const;

int counter(TreeNode *);

int leafCounter(TreeNode *);

int getTreeHeight(TreeNode* nodePtr);

int countNodes(TreeNode *&nodePtr) ;

int countLeaves(TreeNode* nodePtr);

public:

//Constructor

BinaryTree()

{root = NULL;}

//Destructor

~BinaryTree ()

{destroySubTree(root);}

//Binary tree operations

void insertNode(T);

bool searchNode(T);

void remove(T);

int treeHeight();

int numNodes();

int numLeafNodes();

void displayInOrder() const

{displayInOrder(root);}

void displayPreOrder() const

{displayPreOrder(root);}

void displayPostOrder() const

{displayPostOrder(root);}

// Node counter

int counter()

{

int n = counter(root);

return n;

}

// Leaf counter

int leafCounter()

{

int leaf = leafCounter(root);

return leaf;

}

// Height of the tree

int height()

{

int h = treeHeight();

return h;

}

};

//**********************************************************

//Insert accepts a TreeNode pointer and a pointer to a node*

//The function inserts the node into the tree pointed to by*

//the TreeNode pointer. This function is called recursively*

//**********************************************************

template <class T>

void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)

{

if (nodePtr == NULL)

nodePtr = newNode; // Insert the node

else if (newNode->value < nodePtr->value)

insert(nodePtr->left, newNode); // Search the left branch

else

insert(nodePtr->right, newNode);// Search the right branch

}

//*******************************************************

//insertNode create as new node to hold num as its value*

//and passes it to the insert function. *

//*******************************************************

template <class T>

void BinaryTree<T>::insertNode(T item)

{

TreeNode *newNode; //Pointer to a new node

//Create a new node and store num in it

newNode = new TreeNode;

newNode->value = item;

newNode->left = newNode->right = NULL;

//Insert the node

insert(root, newNode);

}

//***********************************************

//destroySubTree is called by the destructor. It*

//deletes all nodes in the tree *

//***********************************************

template <class T>

void BinaryTree<T>::destroySubTree(TreeNode *nodePtr)

{

if (nodePtr)

{

if (nodePtr->left)

destroySubTree(nodePtr->left);

if (nodePtr->right)

destroySubTree(nodePtr->right);

delete nodePtr;

}

}

//***********************************************

//searchNode determines if a value is present in*

//the tree. If so, the function returns true. *

//Otherwise, it returns false. *

//***********************************************

template <class T>

bool BinaryTree<T>::searchNode(T item)

{

TreeNode *nodePtr = root;

while (nodePtr)

{

if (nodePtr->value == item)

return true;

else if (item < nodePtr->value)

nodePtr = nodePtr->left;

else

nodePtr = nodePtr->right;

}

return false;

}

//**********************************************

//remove calls deleteNode to delete the *

//node whose value member is thedame as num *

//**********************************************

template <class T>

void BinaryTree<T>::remove(T item)

{

deleteNode(item, root);

}

//**********************************************

//deleteNode deletes the node whose value *

//memeber id the same as num *

//**********************************************

template <class T>

void BinaryTree<T>::deleteNode(T item, TreeNode *&nodePtr)

{

if (item < nodePtr->value)

deleteNode(item, nodePtr->left);

else if (item > nodePtr->value)

deleteNode(item, nodePtr->right);

else

makeDeletion(nodePtr);

}