CODEWITHSUNDEEP
c++recursionbinary-tree
MasqueradeToday
MasqueradeToday

Reputation: 85

Recursion and Constant variables

I am trying to create a method that will tell me the height a binary tree, the easiest way would be to use a recursion, however for some reason one of my variables is getting reset even though I thought I was checking so it would stay constant...
Here is my code

template<class T>
int findHeight(binaryTreeNode<T> , int leftHeight, int rightHeight,
        int maxHeight) {
    if (leftHeight >= rightHeight && leftHeight >= maxHeight) {
        maxHeight = leftHeight;
    }
    else if (leftHeight < rightHeight && rightHeight >= maxHeight) {
        maxHeight = rightHeight;
    }
    if (t != NULL) {
        cout << "current leftHeight " << leftHeight << " current rightHeight "
                << rightHeight << " current maxHeight " << maxHeight << endl;

        findHeight(t->leftChild, ++leftHeight, rightHeight, maxHeight);
        findHeight(t->rightChild, leftHeight, ++rightHeight, maxHeight);
    }
    return ++maxHeight;
}

This is the output I had gotten when I tried this:

current leftHeight 0 current rightHeight 0 current maxHeight 0
current leftHeight 1 current rightHeight 0 current maxHeight 1
current leftHeight 2 current rightHeight 0 current maxHeight 2
current leftHeight 2 current rightHeight 1 current maxHeight 2
current leftHeight 1 current rightHeight 1 current maxHeight 1
current leftHeight 2 current rightHeight 1 current maxHeight 2
current leftHeight 3 current rightHeight 1 current maxHeight 3
Returned value = 1

Can anyone please help me? How can I make it so the maxHeight does not get reset and will hold the largest value found, anytime throughout the recursion.

Upvotes: 0

Views: 1429

Answers (2)

aschepler
aschepler

Reputation: 72271

A function parameter has automatic storage duration (commonly called "on the stack"). This means each call to findHeight has its own variable named maxHeight. You increment one of these local variables right before its lifetime ends. And although you return the incremented value, you don't use that return value in the recursive calls.

Either use a reference parameter, or use the return values from the two recursive calls.

Upvotes: 0

Serge
Serge

Reputation: 6095

Things are simpler:

int findHeight(binaryTreeNode<T> *t){
    return t ? 1 + MAX(findHeight(t->leftChild), findHeight(t->rightChild)) : 0;
}

In your code you have a problem because maxheight is passed by value, not by reference.

Upvotes: 2

Related Questions