I have a question on C++ recursive function

Question

I was watching youtube video of implementing Binary Search Tree and this is the function where I can get the maximum height of tree.

int MaxHeight(BstNode* root) {
    if (root == NULL) {
        return -1;
    }
    return max(MaxHeight(root->left),MaxHeight(root->right))+1;
}

I roughly get how this function get the height but not exactly. I wonder how this function flows....

I thought as soon as the function gets to the end of the node it return -1 and it is incrementing to the root by 1?

You can wonder no more, start the code with a debugger and step through the code one statement at time. That you will see what each call gets and what it returns, including the increments of the height.... But yes, it increments on the way back from a leaf. — Quimby, Jun 19 '23 at 13:28
...or draw a call graph on paper. You can start by non-recursive many functions with different names, where `MaxHeightRoot(BstNode*)` calls `MaxHeightRootLeft(BstNode*)` and `MaxHeightRootRight(BstNode*)` etc. Then you only need to realize that a recursive function is no different from a non-recursive one. It can call other functions (including itself). — 463035818_is_not_an_ai, Jun 19 '23 at 13:39
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — 463035818_is_not_an_ai, Jun 19 '23 at 13:40
I do not understand what your question is. Your post contains a sentence that ends in a "?", but it is not a question. Instead it describes your understanding of the code. The title (where often a quesiton is found) is not a question either in your case. — Yunnosch, Jun 19 '23 at 13:48
Every function call returns to the place where it was called – there is nothing special about recursive functions. The flow is exactly like if you had called a different function.. — molbdnilo, Jun 19 '23 at 14:11
That `return -1;` doesn't jump all the way back to the first call to `MaxHeight`. It returns from the **current** one to **its caller**. — Pete Becker, Jun 19 '23 at 14:47
Are you curious about the "comma operator" in the return statement? — Thomas Matthews, Jun 19 '23 at 17:58

Joan Marcè i Igual · Answer 1 · 2023-06-19T15:14:29.290

If you make a call graph you can probably understand this better:

As you can see the value of B is 0 because we have max(-1, -1) + 1 == 0. You can apply this for all the values and you'll see why the function is implemented like this.

Let's try to understand the returns:

return max(MaxHeight(root->left), MaxHeight(root->right)) + 1: The idea of this return is simple, we get the height of the left branch and the right branch and whoever branch is longer that is the one we count. Then, we add the height of the current node and that is why we do max() + 1 to count the current node.
return -1. In this case root is not a valid node. This return value is combined with what the other return does. The idea here is that a tree with only one node should have height 0. But, because the previous node adds one to the height we need to make sure that invalid_height + 1 == 0. This in the calls gets translated to max(-1, -1) + 1 == 0.
If we defined "the height of a tree with a single node is 1" then our return value would be 0 instead of -1.

While this is correct as far as it goes, it looks like the actual problem is misunderstanding what that `return -1;` does. If you explain where each `return` goes back to you'll have a good answer. — Pete Becker, Jun 19 '23 at 14:50

score 0 · Answer 2 · answered Jun 19 '23 at 21:50

The author of the function considers a BstNode with no children (i.e. left and right children are NULL) to have a height of zero. They implemented this idea by considering a NULL node to have a height of -1. Thus, when we call MaxHeight on a BstNode (call this node root) with no children, we find the greater of MaxHeight(root->left) (which evaluates to -1) and MaxHeight(root->right) (which also evaluates to -1), and add one. Thus we return 0.

I have a question on C++ recursive function

2 Answers2