Troubles with BST recursion (finding height of a tree in C++)

Question

int BST::getLength()
{
    int leftHeight = 0;
    int rightHeight = 0;

    // Empty case
    if (!prev && !dataInit)
        return 0;


    else
    {
        if (left)
        {
            leftHeight = left->getLength();

            std::cout << "leftHeight: " << leftHeight;
            std::cout << std::endl << std::endl;
        }
        if (right)
        {
            rightHeight = right->getLength();

            std::cout << "rightHeight: " << rightHeight;
            std::cout << std::endl << std::endl;
        }

        if (leftHeight > rightHeight)
            return leftHeight + 1;
        else
            return rightHeight + 1;
    }
}

This is a copied function from some website. I've been trying to write this function down on paper to understand the recursion but I can't seem to find myself comprehending. Specifically, I don't understand how leftHeight and rightHeight are incrementing by one if we're recursively calling it before we add 1.

Any help would be appreciated, thanks.

Answer 1

I am not completely sure about the structure of the rest of this code but I will hazard a guess here. It helps if we start thinking of base cases. For a binary tree, that would be the leaf nodes. For a leaf node, the height of its left or right children would be zero and the height of the entire tree including the leaf node is one.

We can then take a step back and consider a general node in the binary tree: the height of the tree starting at this node is max(leftSubTree, rightSubTree) + 1, where the +1 accounts for the current node.