Inorder tree traversal in binary tree in C

Question

In the below code, I'am creating a binary tree using insert function and trying to display the inserted elements using inorder function which follows the logic of In-order traversal.When I run it, numbers are getting inserted but when I try the inorder function( input 3), the program continues for next input without displaying anything. I guess there might be a logical error.Please help me clear it. Thanks in advance...

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

int i;
typedef struct ll
{
  int data;
  struct ll *left;
  struct ll *right;
} node;

node *root1=NULL; // the root node

void insert(node *root,int n)
{
  if(root==NULL) //for the first(root) node
  {
    root=(node *)malloc(sizeof(node));
    root->data=n;
    root->right=NULL;
    root->left=NULL;
  }
  else
  {
    if(n<(root->data))
    {
      root->left=(node *)malloc(sizeof(node));
      insert(root->left,n);
    }
    else if(n>(root->data))
    {
      root->right=(node *)malloc(sizeof(node));
      insert(root->right,n);
    }
    else
    {
      root->data=n;
    }
  }
}

void inorder(node *root)
{
  if(root!=NULL)
  {
    inorder(root->left);
    printf("%d  ",root->data);
    inorder(root->right);
  }
}

main()
{
  int n,choice=1;
  while(choice!=0)
  {
    printf("Enter choice--- 1 for insert, 3 for inorder and 0 for exit\n");
    scanf("%d",&choice);
    switch(choice)
    {
      case 1:
        printf("Enter number to be inserted\n");
        scanf("%d",&n);
        insert(root1,n);
        break;
      case 3:
        inorder(root1);
        break;
      default:
        break;
    }
  }
}

[Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). — unwind, Oct 31 '13 at 10:13

StoryTeller - Unslander Monica · Answer 1 · 2013-10-31T10:20:25.743

Your insert accepts a pointer to a node, which is local to the scope of the function. After insert returns, the root it was called upon remains unchanged. And you get a leak.

If you want the changes insert does to be visible outside of it, start by changing its signature

void insert(node **root,int n)

And calling it like so:

void insert(&root1, n);

That way, it will modify root1 and not a copy of it.

As a rule of thumb, if a function needs to modify something, it should be passed a pointer to it. You function needs to modify a node*, so it should be passed a node**.

EDIT

As unwind pointed out, you could also return the root as a means of updating it

root1 = insert(root1, n);

This of course works only if you need to modify one object.

Also consider *returning* the new root. – unwind Oct 31 '13 at 10:13 — unwind, Oct 31 '13 at 10:13

score 0 · Answer 2 · answered Oct 31 '13 at 09:50

Your allocation code is off, root1 will always stay NULL since the malloc result is only assigned to a local variable. Pass root in as a pointer to pointer.

Additionally you unconditionally malloc left and right, even though there might already be data there, you should call insert immediately and have the called insert handle the malloc just like for root. Again with a pointer to pointer of course.

Finally you else root->data = n doesn't make any sense, it's already n. And I presume you don't want duplicates in your tree? If you do you need to change your code.

score 0 · Answer 3 · answered Oct 31 '13 at 09:50

Pass reference of node * to the insert() so that when new node is allocated, its appropriately updated.

Also, in your insert() function, don't allocate while moving into below tree. If you allocate then your code tries to check the value on that node and proceed again, which is not correct.

Updated code would be:

void insert(node **root_ptr,int n)
    {
    if(root==NULL) //for the first(root) node
    {
        root=(node *)malloc(sizeof(node));
        root->data=n;
        root->right=NULL;
        root->left=NULL;
        *root_ptr = root;
    }
    else
    {
        if(n<(root->data))
        {
        //root->left=(node *)malloc(sizeof(node));
        insert(&root->left,n);
        }
        else if(n>(root->data))
        {
        //root->right=(node *)malloc(sizeof(node));
        insert(&root->right,n);
        }
        else
        {
        root->data=n;
        }
    }
    }

From main() call it as insert(&root1,n);

Inorder tree traversal in binary tree in C

3 Answers3