Binary Search Tree code

The code below is a partial implementation of a Binary Search Tree (BST) class. (It does not show code for insert/delete as these are not required for this problem). Note that this code does not have a member variable storing the size of the tree. The size of a BST is the number of internal nodes. For example, the size of the BST in Question #1 is 7. Add a method to the code, along with any helper functions, to return the size of the BST. (Hint: think recursion!)

Do not make changes to any of the existing functions. Do not change the contents of the search tree. Space to write your new function(s) is given in the end.

template

struct Node

{

Node() : parent_(0), left_(0), right_(0) { }

bool IsRoot() const { return(parent_ == NULL); }

bool IsExternal() const { return((left_ == NULL) && (right_ == NULL)); }

K key_;

Node* left_;

Node* parent_;

Node* right_;

V value_;

};

template

class BinarySearchTree

{

public:

bool Find(const K& key);

int size(); // NEW MEMBER FUNCTION TO BE IMPLEMENTED

private:

Node* Finder(const K& key, Node* node);

Node* root_;

// DECLARE ANY HELPER FUNCTIONS

};

template

bool BinarySearchTree::Find(const K& key) {

Node* node = Finder(key, root_);

if (!node->IsExternal()) // found

return true;

else // not found

return false;

}

template

Node* BinarySearchTree::Finder(const K& key, Node* node) {

if (node->IsExternal())

return(node);

if (key == node->key_)

return(node);

else if (key < node->key_)

return(Finder(key, node->left_));

else

return(Finder(key, node->right_));

}

//new function to be implemented

template

int BinarySearchTree::size() {

}

Space for any helper functions: