Viraj Turakhia - ofcourse it is not possible with just one tree traversal.. that is, unique tree contructionit is not even possible with two traversals in some casesfor example:post-order: aaaaaaaapre-order: aaaaaaaago construct a unique treeBhavin Shah - @Vraj1. lets assume input does not contain duplicate2. jsut to clarify, I always meant both post-order and pre-order are givenViraj Turakhia - w/o duplicates, it should be possible to construct unique tree with any two traversals.don't ask for algo.. can't write it hereBhavin Shah - nope its not possible if you have just post-order and pre-order traversals of binary tree.consider following input:pre-order: abpost-order: bayou need two traversals and one of them has to be in-order.Viraj Turakhia - a is root and b is the only child.. tht's unique representation.. why u think it is not possible?Bhavin Shah - which child...left or right?Viraj Turakhia - thts non-deterministic even wen u draw this tree on paper.. :)Bhavin Shah - @Sagar told me both of them are correct answers.I differ on it, I think there could be only one correct answer so with the available information we can get only this far and we need more information to proceed.
Can we construct a tree by the postorder txyCabDBA
Where small letters are leaf nodeCapital letters are intermediate and root node