How to find the structure of Tree with given Pre Order and Post Order

Question

how can we find unique structure of a tree with given pre order and post order traversal . Please explain in detail with an example ( please give an example with number of nodes > 5 for more understanding )

References
http://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/

https://gateoverflow.in/50608/generate-unique-binary-order-level-order-traversal-explain

Says that no unique tree can be constructed .  But in VIT 2016 admission Test there had a question from this Topic .
Could some one help ? Is it Really not possible ?

Comments

it should be possible if we are given options , right ?

---

Ya through option elimination , we may do but conceptually we can't..

---

@pc the question would have been Binary search tree on 1,2,3 etc upto n. In this case They need not mention inorder traversal because it is implicitly known to be ascending order of numbers itself

Hope this helps :)

Answer 1

NO with only preorder and post order given we cant find a unique tree....
either preorder with inorder or postorder with inorder is required for "unique" tree..

 we have 2nCn/(n+1) binary trees with n nodes(unlabelled).....and we can get a pre order for each one of them.....and if we try to find post order then definitly we will get more than 1 tree satisfying both conditions together

we need inorder also....either we use inorder with pre or post we will get unique tree each time....but it is neccessary to have inorder..because then only 1 tree can satisfy these conditions

let me give an example with 3 nodes..u can generalise it afterwards

say we have three nodes...even if labelled we get 5 binary trees and every binary tree can be a preorder....
preorder ABC..we get 5 trees..
suppose we want post order CBA....u will see we will get 4 out of those 5 trees satisfying both preorder and post order simultaneously
so UNIQUE TREE not possible with only pre and post order given
try to apply inorder condition sayBCA...
only one out of those 4 trees will satisfy all of them together..

Comments

@sudsho how about if we are given options also ? it should be possible then?

---

as said by habib we can solve using intution those questions...but gate should never give it like that...whether u will be given one out of post or pre order along with inorder...or it could be a BST..as we know if u traverse a BST inorder we get increasing order...that types possible

---

Ok :)
Thank you @habibkhan @ sudhsho

---

welcome bro :)