1 Attachment(s)
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
Re: Need Help - Recursive Algorithm
Re: Need Help - Recursive Algorithm
Quote:
Originally Posted by
pradeepc
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.
Re: Need Help - Recursive Algorithm
Thank you , MrViggy and nuzzle. Would be able to provide me the algorithm, that would be great.
Thanks,
Pradeep
Re: Need Help - Recursive Algorithm
Quote:
Originally Posted by
pradeepc
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