So I'm learning about binary trees in this book that I've been reading and one of the exercises asks me to "write recursive definitions that perform a task on arbitrary binary trees (assume that each data item in the tree is a single integer and that there is no duplicates):
a. Count the number of nodes in the tree (Hint: If the tree is empty, the count is 0. If the tree is not empty, the count is 1 plus the number of nodes in the root's left subtree plus the number of nodes in the root's right subtree.)
c. Find the maximum element
I did the other parts of this problem on my own but I can't seem to figure these out....Can anyone help me out? Thanks
heres a recursive function that gets the size of the tree, but it would be more efficient if you saved the size and updated it every time you shuffled a node around, just update the parents of that node (parent, parents parent, parents parents parent, etc)
class* getMaxElement () //replace class with the class holding your bst
{
class * max = this;
while (max->right != nullptr) max = max->right; //assuming right is greater than left, it has to go one way
return max;
}
make sure to change class to the name of your class in that code