Question
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
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
Node
// DECLARE ANY HELPER FUNCTIONS
};
template
bool BinarySearchTree
Node
if (!node->IsExternal()) // found
return true;
else // not found
return false;
}
template
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
}
Space for any helper functions:
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started