iteratively insert into a binary search tree.Debug C++ code

Question

Here is a c++ function to create a BST tree from an array of integers?
It's simple.
Take first element ,make root.
Take next array element and insert it into the tree.
Why is the loop starting from i=2 and not i=1??

node* buildtree(int a[], int len)
{
    node* root=new node(a[0]);
    node* temp=root;
    for(int i=1;i<len;i++)
    {
        while(!(root->left==NULL && root->right==NULL))
        {
            cout<<"here"<<i<<" "<<a[i]<<"  " << root->val<<"\n";
            if(root->val>a[i])
                root=root->left;
            else
                root=root->right;
        }
        node* currnode=new node(a[i]);
        if(root->val>a[i]) 
            root->left=currnode;
        else
            root->right=currnode;  

        if(root==NULL)
            cout<<"error...never.here";
        root=temp;
    }
    return root;
}

Thanks a lot for explaining it.I tried it another way but it only finds the root.What's the problem in it?

   node* buildtree(int a[],int len)
   { node*  root=new node(a[0]);
    node* curr;
    for(int i=1;i<len;i++)
     { curr=root;
       while(curr!=NULL)    
         {
         if(curr->val>a[i])
         curr=curr->left;
         else 
         curr=curr->right;
         }
     curr=new node(a[i]); 
     }  
 return root;             
  }

for loop in your code is starting from i=2 , not i=1. Is it a typo? — MARK
– MARK, Commented Feb 20, 2012 at 19:33

grundprinzip · Accepted Answer · 2012-02-20 19:31:08Z

1

Because in the first iteration of the loop the while condition is not true because the root node has no child nodes.

while(!(root->left==NULL && root->right==NULL)

for i=1 the left and the right node are NULL and the left node is populated at the end of the first iteration.

answered Feb 20, 2012 at 19:31

grundprinzip

2,5012 gold badges21 silver badges35 bronze badges

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

2 Comments

rakesh99 Over a year ago

@grudprinzip thanks..it was so silly of me not to have noticed.

rakesh99 Over a year ago

but why is the code not working properly,though root is never null in the loop still segmentation fault occurs

Daniel Fischer · Accepted Answer · 2012-02-20 20:59:04Z

When trying to find the point of insertion,

while(!(root->left==NULL && root->right==NULL))
{
    cout<<"here"<<i<<" "<<a[i]<<"  " << root->val<<"\n";
    if(root->val>a[i])
        root=root->left;
    else
        root=root->right;
}

you only stop if both children are NULL, so at some point or other, you will set root to NULL. Consider the array begins with [5, 3, 6, ... ]. You start with

NULL <- node(5) -> NULL
node(3) <- node(5) ->NULL

and then try to insert the 3. Since not both children are NULL, the while loop runs

if (5 > 7)  // false
    root = root->left;
else
    root = root->right;  // now root == NULL, oops

and the controlling condition is checked anew

while(!(NULL->left == NULL && NULL->right == NULL))

segfault likely here, undefined behaviour invoked.

You should do something like

while(true) {
    if (root->val > a[i]) {
        if (root->left == NULL) {
            root->left = new node(a[i]);
            break;
        } else {
            root = root->left;
        }
    } else {
        if (root->right == NULL) {
            root->right = new node(a[i]);
            break;
        } else {
            root = root->right;
        }
    }
}

Collectives™ on Stack Overflow

iteratively insert into a binary search tree.Debug C++ code

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related