Odtnhj

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.

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.