The code below is a partial implementation of a Binary Search Tree (BST) class.
ID: 3715902 • Letter: T
Question
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<typename K, typename V>
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<typename K, typename V>
class BinarySearchTree
{
public:
bool Find(const K& key);
int size(); // NEW MEMBER FUNCTION TO BE IMPLEMENTED
private:
Node<K, V>* Finder(const K& key, Node<K, V>* node);
Node<K, V>* root_;
// DECLARE ANY HELPER FUNCTIONS
};
template<typename K, typename V>
bool BinarySearchTree<K, V>::Find(const K& key) {
Node<K, V>* node = Finder(key, root_);
if (!node->IsExternal()) // found
return true;
else // not found
return false;
}
template<typename K, typename V>
Node<K, V>* BinarySearchTree<K, V>::Finder(const K& key, Node<K, V>* 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<typename K, typename V>
int BinarySearchTree<K,V>::size() {
}
Space for any helper functions:
Explanation / Answer
Algorithm For Size() of BST :
//size() method to return the number of internal nodes
template<typename K, typename V>
int BinarySearchTree<K,V>::size() {
Node<K, V>* node;//create a node to know number of internal nodes
node =root_;//treating node as root node
int siz=0;//initializing size of tree is zero
if(node != NULL) //if node is not null
{
if(!(node->left_ == NULL )) //if node has left child then again calling size() method recursively
size();
if(!(node->right_ == NULL )) //if node has right child then again calling size() method recursively
size();
siz=siz+1; //if a leaf node found then siz is increased by 1.
}
return siz; //returning siz to size() called method
}//end of size() mehod
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.