PostOrder Transversal binary search tree?

This is a discussion on PostOrder Transversal binary search tree? within the C Programming forums, part of the General Programming Boards category; 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) ...

  1. #1
    Registered User
    Join Date
    Jun 2012
    Posts
    2

    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 ?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    Quote Originally Posted by kevin99
    code for post order transversal
    Weirdly enough, you named your function "preorder" and implemented pre-order traversal

    Quote Originally Posted by kevin99
    Now what will happen after returning in which statement control will be passed ?
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2012
    Posts
    2
    Quote Originally Posted by laserlight View Post
    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 ?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    Quote Originally Posted by kevin99
    when it would have printed node 1 that time rt would point to node 1 of the tree.
    That is true. However, this rt is the rt belonging to the stack frame of the function call preorder(rt->lchild), where rt->lchild is the node with value 1. The rt in that context is the node with value 3, so the next function call will the preorder(rt->rchild), where rt->rchild is the node with value 6.

    Quote Originally Posted by kevin99
    now preorder(ptr->lchild) is null null will be passed rt will be NULL .. then how will it get back to node 3 ?
    Remember, whenever you talk about rt, you are talking about it within a certain context. Once the function returns, it is a new (or should I say old?) context, so the rt is different.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree-search method help?
    By shocklightning in forum C++ Programming
    Replies: 5
    Last Post: 03-25-2012, 11:57 PM
  2. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. Binary Search Tree
    By Pyrce in forum C Programming
    Replies: 1
    Last Post: 09-23-2005, 07:04 AM
  5. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 03:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21