CODEWITHSUNDEEP
data-structurestree
zukes
zukes

Reputation: 411

how to create tree whose post and in order traversal is known?

how to create a tree from following post and in order traversed path

In-order : INFORMATION
POST-ORDER : INOFMAINOTR

i know that all the left side elements from R will be the left sub-tree of Root 'R' and right side elements will be the right sub tree of root R but i don't know how to proceed further can any one please help me with step by step instruction thanks.

Upvotes: 1

Views: 193

Answers (1)

Sunil Bojanapally
Sunil Bojanapally

Reputation: 12658

Step 1: Locate last letter in Post-Order, let it be X; which is root.
Step 2: Locate X in In-Order. Letters left to X form left sub tree & Letters to the rught of X form right sub tree.
Step 3: Repeat step 1, 2 for each node.

All the logic becomes simple when you find step 2 for the second iteration.

Upvotes: 2

Related Questions