Recursion and Constant variables

Question

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.

Mind your oxymorons. Constants are not variable, and variables are not (necessarily) constant. Your problem is that you are passing a variable by value, which makes a copy. Changing the copy does not change the variable that it was copied from. — Jive Dadson
– Jive Dadson, Commented Oct 21, 2012 at 4:28

Serge · Accepted Answer · 2012-10-21 04:22:33Z

2

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.

answered Oct 21, 2012 at 4:22

Serge

6,09520 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

aschepler · Accepted Answer · 2012-10-21 04:27:21Z

0

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.

answered Oct 21, 2012 at 4:27

aschepler

72.5k11 gold badges114 silver badges174 bronze badges

Collectives™ on Stack Overflow

Recursion and Constant variables

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related