CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    Join Date
    Sep 2012
    Posts
    2

    Resolved Need Help - Recursive Algorithm

    Hi,

    Could you please help me with the below algorithm ? I have constructed binary tree, but i am not well versed with the algorithm and also check if the binary tree (attached) is correct .

    Given Postorder & Inorder traversals. Construct the binary tree & write recursive algorithm for tree traversals (Consider all three traversals).
    Postorder : IHGFEDCBA
    Inorder : GHIFEDCBA

    Thanks in advance,

    Regards,
    Pradeep
    Attached Images Attached Images  

  2. #2
    Join Date
    Feb 2002
    Posts
    4,640

    Re: Need Help - Recursive Algorithm


  3. #3
    Join Date
    May 2009
    Posts
    2,413

    Re: Need Help - Recursive Algorithm

    Quote Originally Posted by pradeepc View Post
    is correct .
    It looks right to me.

    Postorder has this recursive structure:

    Left branch.
    Right branch.
    Print.

    It visits all nodes all way down to I. Then it retracts while printing in reverse order from I and up.

    Inorder looks like this:

    Left branch.
    Print.
    Right branch.

    It visits the left nodes all way down to G where it prints and continues to the right. Since the nodes below G don't have a left branch they get printed too on the way down to I. Then it retracts while printing all nodes above G in reverse order on the way back up.

  4. #4
    Join Date
    Sep 2012
    Posts
    2

    Re: Need Help - Recursive Algorithm

    Thank you , MrViggy and nuzzle. Would be able to provide me the algorithm, that would be great.

    Thanks,
    Pradeep

  5. #5
    Join Date
    May 2009
    Posts
    2,413

    Re: Need Help - Recursive Algorithm

    Quote Originally Posted by pradeepc View Post
    Would be able to provide me the algorithm, that would be great.
    Recursive binary tree traversal is very standard. Examples are all over internet, like here for example,

    http://www.augustana.ualberta.ca/~ha...traversal.html
    Last edited by nuzzle; September 5th, 2012 at 09:59 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured