BabaSvoloch - 1 year ago 93

C++ Question

Having trouble understanding an explanation of how to find the height of a binary search tree using a recursive function of type int.

For any binary search tree, given a pointer to the root node of the tree, where Node is defined conventionally as follows...

`struct Node {`

int data;

Node* left;

Node* right;

}

Node* root;

we can use the following recursive function of type int to give us the height of the binary search tree... (the function 'max' just takes two ints and returns the greater of the two)

`int findHeight(Node* root){`

if(root == NULL){

return -1;

}

return max(findHeight(root->left),findHeight(root->right)) + 1;

}

int max(int a, int b){

if (a > b)

return a;

else

return b;

}

My understanding is that findHeight(root->left) finds the height of the left subtree of root, findHeight(root->right) finds the height of the right subtree of root, and then max returns whichever is greater, since that will be the overall height of the tree, plus one to include the edge that connects root to that subtree.

I'm pretty new to recursion, so I decided to just unpack one of the recursive function calls and try to understand it. I wrote out findHeight(root->left) in a sort of pseudo-code way, with the word "PAUSE" in it every time the function called itself, to represent what was happening on the stack and indented the next function call to show a new stack frame... (in my sample BST the height of the left subtree was 2)

`int fH(Node* root){`

if(root == NULL)

return -1;

fH(root->left);

PAUSE

int fH(Node* root){

if root == NULL)

return -1;

fH(root->left);

PAUSE

int fHR(Node*root){

if (root == NULL)

return -1;

fH(root->left);

PAUSE

int fHR(Node* root){

if (root == NULL)

return -1;

fH(root->left);

PAUSE

int fHR(Node* root){

if(root==NULL)

return -1;

}

}

}

}

}

The function works correctly, but I don't understand how the return value of the function is growing from -1, which is what the final execution of the function returns, to 2. Do recursive int functions add 1 to their return value every time they return to their preceding stack frame?

I don't see anything in that short function that increments the return value of the function. The only thing I see is that it's -1 for the final call.

If anyone could try to explain this to me I would really appreciate the help. Thank you very much.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

Consider this tree,

```
5
/ \
3 10
/ \ /
2 4 8
```

The function will be called with root which is `5`

.

Then it will be called with `3`

, `2`

(left child `3`

) and then `4`

(right child `3`

).

`2`

's height evaluates to `max(-1, -1) + 1 = 0`

and returned as the result of `3`

's call to `findHeight(root->left)`

. The same happens with `4`

.

The call to `3`

(`5`

's `findHeight(root->left)`

) now evaluates to `max(0, 0) + 1 = 1`

.

So `5`

's left child has a height of `1`

.

The other child (right child) follows the same process where the call to `10`

's left child returns a height of `0`

and it's right child returns a height of `-1`

. `max(0, -1) + 1 = 1`

which will be returned to `5`

's call to `findHeight(root->right)`

.

Now back at the top, `5`

's height is evaluated as `max(1,1) + 1 = 2`

.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**