Unable to print elements in binary search tree

Question

My code is not printing the elements of binary search tree:

//x is the element to be inserted
//structure of program
 typedef struct BST
  {
  int info;
  struct  BST *left;
//pointer to left node

 struct BST *right;
//pointer to right node

 }
 bst;
//global root variable

bst *root;
void insert(int x)
{
    bst *ptr,*sptr=root;
    ptr=(bst*)malloc(sizeof(bst));
    ptr->info=x;
    if(root==NULL)
    {
        ptr->left=ptr->right=NULL;
        root=ptr;
    }
    while(sptr!=NULL)
    {
        if(x<sptr->info)
        {
            sptr=sptr->left;
        }
        else
            sptr=sptr->right;
    }
    sptr=ptr;
}

edit:

 //following is the show function

   void show()
   {
    bst *ptr=root;
    while(ptr!=NULL)
    {

    //it will print untill the ptr is null

      printf("%d",ptr->info);
      ptr=ptr->left;
      ptr=ptr->right;
    }
  }

Standard Warning : Please [do not cast](http://stackoverflow.com/q/605845/2173917) the return value of `malloc()` and family in `C`. — Sourav Ghosh, Apr 27 '15 at 12:16
Can you post the complete code, where you call your functions, and where you have defined your structs? — Ayushi Jha, Apr 27 '15 at 12:34
The problem is within in the `insert` function. The logic of that function is broken. — Jabberwocky, Apr 27 '15 at 12:55

Daniel Siebert · Accepted Answer · 2015-04-27T13:19:27.397

Where is the value of root coming from? You're not passing in the value anywhere? Also, it is tough to help when we don't know the design of type bst.

It appears that you have the right idea. Create a node, and give it some data. If the root is null, then the new value is the root of the BST. After that you go ahead and find the first null node either in the left or right subtree of the root using the standard BST behavior. Finally, when you reach the end you go ahead and insert the last node in the proper place.

void insert(int x)
{
    bst *ptr, *sptr=root; //<-- the value right here?
    ptr = malloc(sizeof(bst));
    ptr->info = x;
    if(root == NULL)
    {
        ptr->left=ptr->right=NULL;
        root=ptr;
    }

    while(sptr!=NULL)
    {
        if(x<sptr->info)
        {
            sptr=sptr->left;
        }
        else
            sptr=sptr->right;
    }
    sptr=ptr; // <-- What is this line trying to do?
}

However, where did your updated tree go?

Since in C everything is passed by value, you're running into the problem where you're not seeing your updated tree after you leave this function. You need to go ahead and change the function to return a bst* type, and also maintain the root node during the entire function. Now the first line of code (*sptr = root) makes more sense! Finally, you were not setting the left and right fields of ptr to NULL. This means you were jumping over your if statements.

bst* insert(int x, bst *root)
{
    bst *ptr, *sptr=root;
    ptr = malloc(sizeof(bst));

    ptr->left = NULL;
    ptr->right = NULL;

    ptr->info = x;
    if(root == NULL)
    {
        ptr->left=ptr->right=NULL;
        root=ptr;
        return root;
    }

    while(sptr!=NULL)
    {
        if(x<sptr->info)
        {
            sptr=sptr->left;
        }
        else
            sptr=sptr->right;
    }
    sptr=ptr;
    return root;
}

What about the next function?

I just started looking at this one too. I am not used to the global variables in c, so I will go ahead and make two modifications. Let's make this recursive, and pass in the value of the root rather than using the global.

void show(bst *root)
{
    if(root == NULL){
         return;
    }
    printf("%d",root->info);
    show(root->left);
    show(root->right);
 }

This will take in some value, and solve the tree recursively, and print as it reaches each node. Thus, it will print the root node (if it exists), and then print the left entire left subtree before it prints the right subtree.

Finally, looking at your main

I added the local variable root and thus you will have to remove the global variable named root outside of your main function. I also set the value of it to null so your first insert will fire correctly.

int main()
{
  int i,n,x;
  bst *root = NULL; //<-- I added this line of code to remove the global
  puts("Enter number of elements");
  scanf("%d",&x);

  for(i=0;i<x;i++)
  {
      puts("Enter elements");
      scanf("%d",&n);
      root = insert(n, root);
  }
show(root);
return 0;
}

I hope this helps!

root is global variable typedef struct BST { int info; struct BST *left; struct BST *right; } bst; bst *root; — Dumb, Apr 27 '15 at 12:59
I used to be a TA for CS1 a few years ago and this is bringing back memories :) — Daniel Siebert, Apr 27 '15 at 12:59
Dumb, can you go ahead and add the code in the first paragraph using the code indentation, it would be a lot easier to read! — Daniel Siebert, Apr 27 '15 at 13:02
I am not asking you to edit my code ,i am just asking you to check the mistake and point me ,as this page is asking me to add more and more details so I am unable to edit here — Dumb, Apr 27 '15 at 13:15
My last comment wasn't constructive, I apologize. On the other hand I am trying to help you in more ways than one. I have rewritten a lot of code, but I feel like I have also given strong justification why when I have. I have only changed a few lines of code in each function and you should be able to make the changes yourself, good luck! — Daniel Siebert, Apr 27 '15 at 13:22
I am getting you , My teacher is just like you,he helps me in the same way rather than spoon feed me — Dumb, Apr 27 '15 at 13:24
You have a good teacher then :) . Please let me know if you get this working! — Daniel Siebert, Apr 27 '15 at 13:26

Unable to print elements in binary search tree

1 Answers1