0

This is a code to find least common ancestor of n1 and n2 in a binary tree

Node * lca (Node* root, int n1, int n2)
{
  if (root == NULL)
    return NULL;

  if (root->data == n1 or root->data == n2)
    return root;
  
  Node *l = lca(root->left, n1, n2);
  Node *r = lca(root->right, n1, n2);
  
  if (l and r)
    return root;

  //return (l != NULL) ? l : r;
}

I took a random binary tree as shown below

    1
   / \
  2   3
 / \ / \
4  5 6  7

When the function call goes to node with value 5 there is no pointer to node that is returned to the caller function. So what value will be assigned to r in that case?

I tried assuming that by default it returns a NULL pointer, so if (r == NULL), I tried to print a number, but I got no value in output.

I tried using the keyword undefined like in javascript but to no avail. It is showing error. what does it mean to not return any value in a function that has a return type?

Tanishk Goyal
  • 15
  • 4
  • You're using C++17, so you probably want to use `nullptr` not `NULL`. Could we see a definition of the `Node` class? The problem might just be that the node with value 5 has completely uninitialized `left` and `right` pointers, which would be different than having `nullptr` in those places. – Nathan Pierson Jan 14 '23 at 19:48
  • 1
    If the function fails to return a value, the behaviour is [undefined](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior). – n. m. could be an AI Jan 14 '23 at 19:48
  • it is undefined behavior for a function to not return a value when it is supposed to return a value. You can't make any meaningful prediction about the outcome. Don't do this. – JohnFilleau Jan 14 '23 at 19:48
  • 2
    @mkrieger1 It's undefined behavior. In general it's the halting problem to figure out 100% of the time if a function will or will not execute a return statement. – Nathan Pierson Jan 14 '23 at 19:49
  • If you want your function to return some value when some null-case happens, you need to explicitly return that value. – JohnFilleau Jan 14 '23 at 19:50
  • See also [Why does flowing off the end of a non-void function without returning a value not produce a compiler error?](https://stackoverflow.com/questions/1610030/) – JaMiT Jan 14 '23 at 19:51

1 Answers1

2

If you have function that is declared with a return type other than void and in a call to the function the closing } is reached without an intervening return statement, then your program has undefined behavior.

Undefined behavior means that you lose any guarantees on the behavior of the program. Any outcome is possible. It could behave as if you had written return NULL;, it could behave as if returning a random value, it could behave as if the call never happened and it doesn't have to be consistent in any way. This is true not only for the offending function call, but the whole program (with given input), also the parts leading up to the function call. Such a program is simply invalid and broken. It is pointless to think about its behavior.

So don't do that. Compilers will warn you about the possibility of running off the end of a non-void function if you enable warnings. If yours didn't, then check how to enable a higher warning level for your compiler.

I tried using the keyword undefined like in javascript but to no avail.

There is no equivalent to that in C++.

Also, if you are coming from javascript, then you need to be especially careful, since javascript (as far as I know) has no equivalent of C's and C++'s undefined behavior. Understanding the significance of this concept and remembering which situations cause it, is something that new users of the language coming from other languages often seem to have problems with. In C and C++ you are not guaranteed to be notified with a warning or error at either compile- or runtime if your program is broken. It will simply have arbitrary behavior that may or may not seem to work as expected under undefined behavior.

user17732522
  • 53,019
  • 2
  • 56
  • 105