CODEWITHSUNDEEP
crecursionstructbinary-search-treefunction-definition
Achyut Jagini
Achyut Jagini

Reputation: 73

My binary search tree c program has a problem.I am using inorder traversal.only root node printed why?

it is a binary search tree with inorder traversal.there is an issue while printing elements. I can't solve the issue.Only the root is gettting printed.it could be a semantic error also.Maybe there is issue in inserting.or some issue in displaying inorderly.

 #include<stdio.h>
    #include<stdlib.h>
    struct node
    {
        int data;
        struct node *llink;
        struct node *rlink;
    };
    typedef struct node bstnode;
    bstnode *root=NULL;

void insert(int ele)
{
    bstnode *cur,*prev,*temp;
    temp=(bstnode *)malloc(sizeof(bstnode));
    temp->data=ele;
    temp->llink=temp->rlink=NULL;
    cur=root;
    prev=NULL;
    if(root==NULL)
       root=temp;
    else
    {  
        prev=cur;
        while(cur!=NULL)
        {
         if(ele<cur->data)
            cur=cur->llink;
         else
           cur=cur->rlink;
        }
    if(ele<prev->data)    
      prev->llink=temp;
       else
        prev->rlink=temp;
    }
    //return root; 
}

void inorder()
{
if(root==NULL)
{
    return;}
else{
inorder(root->llink); 
printf("\n%d",root->data);
inorder(root->llink);
}
}

int main()
{
    insert(45);
    insert(76);

    inorder();
}

Upvotes: 1

Views: 52

Answers (2)

MikeCAT
MikeCAT

Reputation: 75062

Firstly, the part

        prev=cur;
        while(cur!=NULL)
        {
         if(ele<cur->data)
            cur=cur->llink;
         else
           cur=cur->rlink;
        }

is wrong.

Due to the wrong place of prev=cur;, prev will be only root instead of pointing at the node to be the parent of the new node. The statement should be inside the loop:

        while(cur!=NULL)
        {
         prev=cur;
         if(ele<cur->data)
            cur=cur->llink;
         else
           cur=cur->rlink;
        }

Secondly, the function inorder is wrong. It is executed unconditionally when root != NULL.

Instaed of ignoring arguments and print root infinitely, it should take an argument to specify which node should be printed.

Using llink twich is also weird.

It can be like this:

void inorder(bstnode* node)
{
    if(node==NULL)
    {
        return;
    }
    else{
        inorder(node->llink); 
        printf("\n%d",node->data);
        inorder(node->rlink);
    }
}

And inorder(); in the main function should be inorder(root);.

Upvotes: 1

Vlad from Moscow
Vlad from Moscow

Reputation: 310930

In this code snippet

else
{  
    prev=cur;
    while(cur!=NULL)
    {
     if(ele<cur->data)
        cur=cur->llink;
     else
       cur=cur->rlink;
    }
if(ele<prev->data)    
  prev->llink=temp;
   else
    prev->rlink=temp;
}

there is a logical mistake. The statement

    prev=cur;

shall be within the following while statement. For example

    while(cur!=NULL)
    {
     prev=cur;
     if(ele<cur->data)
        cur=cur->llink;
     else
       cur=cur->rlink;
    }

And the function inorder. Also incorrect because it is declared without a parameter

void inorder()
{
if(root==NULL)
{
    return;}
else{
inorder(root->llink); 
printf("\n%d",root->data);
inorder(root->llink);
}
}

Also there is used the data member llink two times.

It should be declared and defined like

void inorder( const bstnode *node )
{
    if ( node )
    {
        inorder( node->llink ); 
        printf( "\n%d", node->data );
        inorder( node->rlink );
    }
}

And it is called like

inorder( root );

Upvotes: 1

Related Questions