Why return pointer to object if pointer is modified within function?

Question

I found this snippet of code from GeeksForGeeks on importing nodes into a tree from a array-representation of a tree.

I tried implementing my own version of this but couldn't make it work. Then I realized that I must return Node* (in my own version: treeNode*).

Why do I have to do this If I'm already modifying the pointer (root) within the function?

From GeeksForGeeks:

// Function to insert nodes in level order 
Node* insertLevelOrder(int arr[], Node* root, int i, int n) 
{ 
    // Base case for recursion 
    if (i < n) 
    { 
        Node* temp = newNode(arr[i]); 
        root = temp; 

        // insert left child 
        root->left = insertLevelOrder(arr, 
                   root->left, 2 * i + 1, n); 

        // insert right child 
        root->right = insertLevelOrder(arr, 
                  root->right, 2 * i + 2, n); 
    } 
    return root; 
}

My Own Version:

treeNode* import_treeNode(treeNode* root, int nodes[], int curr_i, int size){
    if (curr_i < size){
        treeNode newNode = treeNode(nodes[curr_i]);
        root = &newNode;
        root->left = import_treeNode(root->left, nodes, 2 * curr_i + 1, size);
        root->right = import_treeNode(root->right, nodes, 2 * curr_i + 2, size);
    }
    return root;
}

My version does not work because it doesn't successfully return a treeNode with values set. I can verify that the treeNode constructor does work. The problem lies in root->left = import_treeNode doesn't successfully set the left node, and same for the right node.

the reason is that the function "insertLevelOrder" modifies value of argument pointer, not the actual pointer pointing to the bst root. to fully understand the difference you need to know the difference between "pass by value" and "pass by reference" — mangusta
– mangusta, Commented Nov 11, 2018 at 4:36

aschepler · Accepted Answer · 2018-11-11 04:32:23Z

1

You are returning a pointer to a local variable, whose lifetime has already ended.

treeNode* import_treeNode(treeNode* root, int nodes[], int curr_i, int size){
    if (curr_i < size){
        // The lifetime of "newNode" begins when its constructor completes.
        treeNode newNode = treeNode(nodes[curr_i]);
        root = &newNode;
        // Now root points at newNode.
        root->left = import_treeNode(root->left, nodes, 2 * curr_i + 1, size);
        root->right = import_treeNode(root->right, nodes, 2 * curr_i + 2, size);
        // The above are the same as just assigning newNode.left and newNode.right.

        // Here the destructor is invoked for "newNode", and its lifetime ends.
    }
    // Returns a dangling pointer, which once pointed at newNode.
    // Using that pointer in almost any way results in undefined behavior.
    return root;
}

It would be better to use a std::unique_ptr<treeNode> or std::shared_ptr<treeNode>, which are harder to accidentally leave as dangling pointers. Or if you must use raw pointers, then you would at least need to create a treeNode object using the new keyword, so that its lifetime can last longer than a function call.

answered Nov 11, 2018 at 4:32

aschepler

72.5k11 gold badges114 silver badges174 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Timothy Huang Over a year ago

Why does the GeeksForGeeks version work then if it returns root, a Node* pointer, exactly like I'm doing in mine?

John Perry Over a year ago

@TimothyHuang We'd have to see the code to be sure, but the GeeksForGeeks code initializes a new pointer in newNode(arr[i]);. Also, notice that they have Node *temp while you have treeNode newNode -- they're initializing a pointer, while you're initializing a local variable. I'd also be really worried about whether that local variable is initialized properly.

John Perry Over a year ago

@aschepler has hit the nail on the head. This is a common C++ mistake, and often hard to debug, especially for beginners. Other languages don't have this problem because everything is a reference/pointer.

David Schwartz Over a year ago

Your code saves the address of newNode, which is the address of an object that will cease to exist as soon as you hit the } after the if. The example code does not make that mistake as it does not create a local object of type Node instead creating a local object of type Node*.

Collectives™ on Stack Overflow

Why return pointer to object if pointer is modified within function?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related