Problem in inorder traversal in binary search tree ...?

[Rubinder singh]

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

In the above code if we reach to the leaf(i.e last element of the tree which has no further childs) inorder(r->left); will return null value and it will return the 0 value and the code will proceed to the print statement and will print the element........

But it will go to the inorder(r->right); statement it will also return 0 value(as this is the leaf) and complier will come out of the function with only one value printed....


But instead what happens is goes back to the previous element and print that

plz tell me the reason ?

Thanks

[Peter87]

I don't see a problem with your code. Are you sure your pointers are pointing correctly?

[hamsterman]

Consider a tree

   A
 /  \
B    C

inorder(A) expands to

inorder(B);
printf("\t %d",A->data);
inorder(C);

Then inorder(B) and (C) both expand to printf("\t %d", B/*or C*/->data);
So finally you have

printf("\t %d",B->data);
printf("\t %d",A->data);
printf("\t %d",C->data);

Of course in reality things don't 'expand'. I'm hoping this will be easier to understand this way. What really happens is when you call a function, after it does it's work, program execution returns to where it was.