Pass and Return 'Reference to a Pointer' for Binary Search Tree Insertion in C-CodePudding

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode*& node = find(root, val);
        node = new TreeNode(val);
        return root;
    }
    TreeNode*& find(TreeNode*& root, int& val) {
        if (root == nullptr) return root;
        else if (root->val > val) return find(root->left, val);
        else return find(root->right, val);
    }
};

I am learning C and read this code on a lecture slide. The code is about the insertion of a new node into a binary search tree. The idea is to find the target location and then insert a new node to the location. I can understand the reason for the 'find' function returning a 'reference to pointer' type. I think it is because we need to modify the address of the target location after the 'find' function returns. However, I don't know why we need to use the 'reference to pointer' type also when we pass the root node into the 'find' function. If I change TreeNode*& find(TreeNode*& root, int& val) to TreeNode*& find(TreeNode* root, int& val), the program will return the original tree without the target insertion. Can anyone help with this question? Thank you in advance!

CodePudding user response：

If you change find to TreeNode*& find(TreeNode* root, int& val) then look at the first line of the function:

    if (root == nullptr) return root;

This would return a reference to a local variable. Changing it in insertIntoBST is undefined behavior and will not change the root variable inside insertIntoBST.

Go through the code step by step when inserting the first value into an empty tree:

NodeTree *tree = nullptr;
tree = insertIntoBST(tree, 42);

The insertIntoBST function could use the same trick as find and modify the root in place:

void insertIntoBST(TreeNode*& root, int val) {
    TreeNode*& node = find(root, val);
    node = new TreeNode(val);
}

NodeTree *tree = nullptr;
insertIntoBST(tree, 42);
insertIntoBST(tree, 23);
insertIntoBST(tree, 666);

or even shorter:

void insertIntoBST(TreeNode*& root, int val) {
    find(root, val) = new TreeNode(val);
}