CODEWITHSUNDEEP
c++data-structures
Timothy Huang
Timothy Huang

Reputation: 21

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

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.

Upvotes: 0

Views: 237

Answers (1)

aschepler
aschepler

Reputation: 72271

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.

Upvotes: 1

Related Questions