CODEWITHSUNDEEP
cbinary-treebinary-search-tree
Rupesh
Rupesh

Reputation: 81

Binary Search Tree insertion/traversal not functioning properly

I'm trying to implement BST by inserting a few elements (5,8,10,20,30), and printing them by inorder traversal. But the output is:

5 8 30 20 8 30 10 5 8 30 20 8 30

instead of:

5 8 10 20 30

I tried to debug the code, but it seems to malfunction at the inorder traversal part even though it's correct(in my opinion).

Here's the code:

#include<stdio.h>
#include<stdlib.h>

struct tree{
struct tree *lchild, *rchild;
int data;
}*root=NULL;

void insert(int key)
{
struct tree *tail,*new,*temp=root;
if(root==NULL)
{
    new=(struct tree*)malloc(sizeof(struct tree));
    new->data=key;
    new->lchild=new->rchild=NULL;
    root=new;
    return;
}
else{       
    while(temp!=NULL)
    {
        tail=temp;
        if(key<temp->data)
            temp=temp->lchild;
        else if(key>temp->data)
            temp=temp->rchild;
        else
            return;
    }
    new=(struct tree*)malloc(sizeof(struct tree));
    new->data=key;
    new->lchild=new->rchild=NULL;
    
    if(key<tail->data)
        tail->lchild=new;
    tail->rchild=new;
    }

}

void inOrder(struct tree *temp)
{
    if(temp)
    {
    inOrder(temp->lchild);
    printf("%d ",temp->data);
    inOrder(temp->rchild);
    } 
}

int main()
{
insert(10);  
insert(5);
insert(20);
insert(8);
insert(30);

inOrder(root);
return 0;

 }

Upvotes: 0

Views: 27

Answers (1)

wildplasser
wildplasser

Reputation: 44230

Change

if(key<tail->data)
        tail->lchild=new;
tail->rchild=new;

To

if (key<tail->data) tail->lchild=new;
else tail->rchild=new;

The joy of pointer-to-pointer:

void insert(int key)
{
struct tree **pp, *new;

    for ( pp = &root; *pp ;  ) {
        if (key < (*pp)->data)
            pp = &(*pp)->lchild;
        else if (key > (*pp)->data)
            pp = &(*pp)->rchild;
        else return;
    }

    new = malloc(sizeof *new );
    new->data = key;
    new->lchild = new->rchild = NULL;
    *pp = new;

    return;
}

Upvotes: 1

Related Questions