Modify the binary search tree created in the precious programming challenge to add a member function

int size()

that returns the number of items (nodes) stored in the tree. Demonstrate the correctness of the new member function with a suitable driver program.

Previous program:

#include

using namespace std;

class BinarySearchTree

{

private:

struct BST

{

BST* left;

BST* right;

int data;

};

BST* root;

public:

BinarySearchTree()

{

root = NULL;

}

bool isEmpty() const { return root == NULL; }

void print_inorder();

void inorder(BST*);

void insert(int);

void search(int);

};

void BinarySearchTree::search(int d)

{

bool found = false;

if (isEmpty())

{

cout << " This Tree is empty " << endl;

return;

}

BST* curr;

BST* parent;

curr = root;

while (curr != NULL)

{

if (curr->data == d)

{

found = true;

break;

}

else

{

parent = curr;

if (d>curr->data) curr = curr->right;

else curr = curr->left;

}

}

if (!found)

{

cout << " Data not found " << endl;

}

else

cout << "Number " << d << " is found" << endl;

}

void BinarySearchTree::insert(int d)

{

BST* t = new BST;

BST* parent;

t->data = d;

t->left = NULL;

t->right = NULL;

parent = NULL;

if (isEmpty()) root = t;

else

{

BST* curr;

curr = root;

while (curr)

{

parent = curr;

if (t->data > curr->data) curr = curr->right;

else curr = curr->left;

}

if (t->data < parent->data)

parent->left = t;

else

parent->right = t;

cout << "Number " << d << " is inserted into tree" << endl;

}

}

void BinarySearchTree::print_inorder()

{

inorder(root);

}

void BinarySearchTree::inorder(BST* p)

{

if (p != NULL)

{

if (p->left) inorder(p->left);

cout << " " << p->data << " ";

if (p->right) inorder(p->right);

}

else return;

}

int main()

{

BinarySearchTree bst;

int ch, insert, selement;

while (1)

{

cout << endl << endl;

cout << " Simple Binary Search Tree Operations " << endl;

cout << " 1. Insert" << endl;

cout << " 2. Search " << endl;

cout << " 3. In-Order Traversal " << endl;

cout << " 4. Exit " << endl;

cout << " Enter your choice : ";

cin >> ch;

switch (ch)

{

case 1: cout << " Enter number to be inserted : ";

cin >> insert;

bst.insert(insert);

break;

case 3: cout << endl;

cout << " In-Order Traversal " << endl;

bst.print_inorder();

break;

case 2: cout << endl;

cout << " Enter number to be search " << endl;

cin >> selement;

bst.search(selement);

break;

return 0;

}

}

}