CODEWITHSUNDEEP
c++data-structuresbinary-search-tree
parth
parth

Reputation: 35

inserting a new element in a binary search tree

I am trying to insert a new element in a binary search tree, i wrote the following function, but it does not seem to work and i cant seem to understand why.

code:

node* new_node(int data)
{
    node* ptr=new node();
    ptr->data=data;
    ptr->left=NULL;
    ptr->right=NULL;
    return ptr;
}
void insert(node* root,int d)
{
    if(root==NULL)
        root=new_node(d);
    else if(d<root->data)
        insert(root->left,d);
    else
        insert(root->right,d);
}

Upvotes: 2

Views: 267

Answers (2)

darkprinx
darkprinx

Reputation: 691

Try this instead-

node* insert(node* root,int d)
{
    if(root==NULL)
        root = new_node(d);
    else if(d<root->data)
        root->left = insert(root->left,d);
    else
        root->right = insert(root->right,d);
    return root;
}

Upvotes: 2

eerorika
eerorika

Reputation: 238351

When you pass an object to a function, the function receives a copy of the value as a parameter. Modifying a copy of a value has no effect on the original object (at least in case of fundamental types like pointers. This doesn't apply to "referential" classes that have internal indirection).

In order to modify an object that is outside of the function, you need to use indirection. You already have a layer of indirection since you pass a pointer. By indirecting through the pointer argument, you can modify the node that is outside the function. But assigning the pointer is not an attempt of modifying the pointed node. It is an attempt at modifying the pointer. But the pointer is a copy, so the assignment has no effect to the outside of the function.

So, you need a second layer of indirection: Pass a reference to the pointer, so that assigning the pointer modifies the referred pointer instead of a copy. Another approach is to use a return value, as demonstrated by Abdullah. Note that this changes how the function should be called slightly.

Upvotes: 4

Related Questions