BabaSvoloch BabaSvoloch - 1 year ago 100
C++ Question

Interpreting the return value of a recursive function of type 'int' in c++

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.

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