Binary tree recursive functions

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
void getTreeSize (int &size)
{
    if (this->right != nullptr)
    {
        size++;
        this->right->getTreeSize(size);
    }
    if (this->left != nullptr)
    {
        size++;
        this->left->getTreeSize(size);
    }
}


1
2
3
4
5
6
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
Topic archived. No new replies allowed.