0

I was solving problem of insertion of node in a binary tree. I have the following doubts:

1) If we are inserting a node then we should return a pointer pointing to that node as then only we will be able to access the node, right?

2) Then here why are we returning root? We must return root->left or root->right accordingly, where am I wrong?

struct node* insert(struct node* root, int data)
    {
        if (root == NULL)    //If the tree is empty, return a new,single node
            return newNode(data);
        else
        {
            //Otherwise, recur down the tree 
            if (data <= root->data)
                root->left  = insert(root->left, data);
            else
                root->right = insert(root->right, data);
            return root;
        }
    }

3) Is this root which the above code returns the changed one from what it was previously due to recursion?

Improve this question
1
  • Try drawing the algorithm out on paper and remembering to add recursive calls to a stack. Commented Oct 8, 2018 at 8:55

2 Answers 2

Reset to default
1

You misunderstand the return value.

The return value of this insert function is a pointer to the subtree that now has data inserted into it. If the passed in root was null, this is a new 1 node tree; if the passed in root is non-null, the return value is the same root.

This makes the recursion a bit simpler. We simply recurse until we run head-on into nullptr in a branch. Then the recursion stops, and the return value sets the parent's left or right node.

To create a brand new tree you type:

node* new_tree = insert(nullptr, 7);

to insert something into an existing tree you type:

existing_tree = insert(existing_tree, 7);

or equivalently

insert(existing_tree, 7);

so long as existing_tree isn't null.

This "double use" of the function (to both create and modify a tree) can confuse, but it makes the specific recursive use a tad less verbose, and makes the "empty tree is a nullptr" and "always do existing_tree = insert(existing_tree, val);" is a rule that makes the empty tree as the null tree work.

This is, however, a very C way of doing things.

A more way of doing things would be:

std::unique_ptr<node> insert(std::unique_ptr<node> root, int data)
{
    if (root == nullptr)    //If the tree is empty, return a new,single node
        return std::make_unique<node>(data);
    else
    {
        //Otherwise, recur down the tree 
        if (data <= root->data)
            root->left  = insert(std::move(root->left), data);
        else
            root->right = insert(std::move(root->right), data);
        return std::move(root);
    }
}

where the flow of data into and out of the function is more explicit, and we assume node has a constructor that takes data.

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

Comments

0

This recursive insert should always return the very root node of the tree. Just because you read return root doesn't mean the original function call has finished executing, it just means the n'th recursion has finished. The recursive calls have all been pushed onto the stack and therefore must all be resolved before the original caller receives the returned value.

You can get back to the inserted node by doing a find for the inserted value.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.