return a local pointer

Question

struct node
{
  Item item; node *l, *r;
  node(Item x) {item = x; l = 0; r = 0;}
};

typedef node* link;
link max(Item a[], int l, int r)
{
    int m = (l+r)/2;
    link x = new node(a[m]);
    if (l==r) return x; // return a local pointer
    x->l = max(a, l, m);
    x-r = max(a, m+1, r);
    Item u = x->l->item, v = x->r->item;
    if (u>v) x->item = u;
    else x->item=v;

    return x;    // return a local pointer
}

This is a piece of code from "Algorithm in c++" by Robert Sedgewick, page 252, Program 5.19. And in function max(), the returned variable is a pointer which is created inside the function.

In my opinion, returning a local pointer is not allowed in c/c++. So my question is that "is that OK to write a function like this"? I cannot believe such a classic book make mistake like this. Or I misunderstood the principle? Please help. Thanks.

Answer 1

x isn't a "local pointer" - that is, a pointer to a local variable. *x was allocated using new. x points to dynamically allocated memory and returning that pointer is just fine. So yes, it's OK to write a function like this one, and there's not an error in the book.

Answer 2

It is an error to return a pointer to a local variable. x points to a variable allocated on the heap:

link x = new node(a[m]);

Thus x isn't pointing to a local variable.

The reason that returning a pointer to a local variable is an error is that such a variable exists for only as long as the function is active (i.e. between it is entered and exited). Variables allocated on the heap (e.g. with the use of the new operator) exist until they are deallocated (e.g. with the delete operator).