Thread: PostOrder Transversal binary search tree?

suppose this is the binary search tree
http://upload.wikimedia.org/wikipedi...earch_tree.svg

code for post order transversal

Code:

void preorder(struct tree *rt)
{
     if(rt==NULL)
     {
                 return;
     }
printf("%d  ",rt->info);
preorder(rt->lchild);
preorder(rt->rchild);
}

It will print 8 then 3 then 1
after printing 1 this statement will execute
preorder(rt->lchild); because the left of node which contains 1 is NULL so in this recursive function preorder(rt->lchild); null will be passed. then root will also become NULL thats why this if statement will execute

Code:

if(rt==NULL)
     {
                 return;
     }

Now what will happen after returning in which statement control will be passed ?

Originally Posted by laserlight

Weirdly enough, you named your function "preorder" and implemented pre-order traversal


The function returns to the caller, which happens to be itself but with a different stack frame. So, preorder(rt->rchild) will be called, where rt is the node with value 3.

oops that was a mistake .. It preorder

when it would have printed node 1 that time rt would point to node 1 of the tree.
now preorder(ptr->lchild) is null null will be passed rt will be NULL .. then how will rt get back to node 3 ?

Each time you make a recursive call, you get another copy of the function context on the stack. By context, I mean the set of function parameters and local variables for that function, and the exact instruction it's executing. All of that information is saved for when you return to this instance of the function. There is one function in your code, but several instances of that function on the stack, each with their own rt parameter, which can all be pointing to different places in the tree. When that function returns, that particular context is gone, but the rest of them remain. You resume executing instructions in the previous stack frame, with the previous context. rt doesn't "get back to node 3", because it's a different rt. The rt that was NULL is no more once that instance of the function returns to it's caller. The rt that pointed to the node with value 3 still points there, it never changed.