Pointer assignment does not work in recursive function

Question

I have a binary tree program, when I am trying to traverse the tree for insertion in a recursive function pointer assignment does not seem to work. First things first here is the inserting function which is not working:

void append(Node* &curr, int val){

    if(curr==nullptr){
        Node* newNode = new Node(val);
        std::cout << "Created new Node with value: " << newNode->value << std::endl;
        curr = newNode;
        return;
    }
    if(curr->value > val){
        curr = curr->left;
        append(curr, val);
    }
    else{
        curr = curr->right;
        append(curr,val);
    }
}

But when I tweak the same function like following, it seems to work just fine:

void append(Node* &curr, int val){
        if(curr==nullptr){
            Node* newNode = new Node(val);
            std::cout << "Created new Node with value: " << newNode->value << std::endl;
            curr = newNode;
            return;
        }
        if(curr->value > val){
            append(curr->left, val);
        }
        else{
            std::cout << "Right" << curr->value << std::endl;
            append(curr->right,val);
        }
    }

I came to fix this after hours of work, and still can't understand why the first function does not work while the second one works as expected. Was hoping anyone can tell me why curr=curr->left is different than passing curr->left to the recursion.

Check this post https://stackoverflow.com/questions/32321766/can-we-initialize-a-pointer-in-a-function-and-still-the-same-address-is-stored-i/32321824#32321824 — Moshe Rabaev, Feb 16 '20 at 18:42
Think about how `curr = newnode` gets the newly allocated node back to the caller. How does that relate to `curr = curr->left`? — 1201ProgramAlarm, Feb 16 '20 at 18:48

score 1 · Accepted Answer · answered Feb 16 '20 at 18:48

1

In this function implementation

void append(Node* &curr, int val){

    if(curr==nullptr){
        Node* newNode = new Node(val);
        std::cout << "Created new Node with value: " << newNode->value << std::endl;
        curr = newNode;
        return;
    }
    if(curr->value > val){
        curr = curr->left;
        append(curr, val);
    }
    else{
        curr = curr->right;
        append(curr,val);
    }
}

As the pointer curr is passed by reference then in these statements

        curr = curr->left;
        curr = curr->right;

the value of the pointer is overwritten.

Pay attention to that the first if statement can be rewritten simpler without introducing an intermediate variable.

    if ( curr == nullptr ){
        curr = new Node(val);
    }

answered Feb 16 '20 at 18:48

Vlad from Moscow

301,070
26
186
335

1

Just to clear my understanding, what I am doing wrong, is that I am trying to assign a value to a reference right ? (And as curr is a reference ' a memory address', I can't just say that the memory address equals to other memory address or a 'pointer' to be precise?) – Priyank Trivedi Feb 16 '20 at 18:59
1

@PriyankTrivedi Let's assume the first call of the recursive function and the pointer to the head node of the list is not equal to nullptr, In this case its value will be overwritten for example by the value of curr->next. So the pointer willl not point to the first node of the list. The address of the first node will be lost. – Vlad from Moscow Feb 16 '20 at 19:03

Pointer assignment does not work in recursive function

1 Answers1