tag:blogger.com,1999:blog-5608594534633161456.post6841175356266696587..comments2016-01-12T13:17:15.091+05:30Comments on Me Versus Self: Construct binary tree using Post-order and Pre-order TraversalsBhavin Shahhttp://www.blogger.com/profile/16257384637763382553noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5608594534633161456.post-17370208649683578782013-09-12T19:34:48.406+05:302013-09-12T19:34:48.406+05:30Where small letters are leaf node
Capital letters ...Where small letters are leaf node<br />Capital letters are intermediate and root nodeAnonymoushttps://www.blogger.com/profile/18216206947293574662noreply@blogger.comtag:blogger.com,1999:blog-5608594534633161456.post-3998228667168116442013-09-12T19:33:15.390+05:302013-09-12T19:33:15.390+05:30Can we construct a tree by the postorder txyCabDBA...Can we construct a tree by the postorder txyCabDBA<br />Anonymoushttps://www.blogger.com/profile/18216206947293574662noreply@blogger.comtag:blogger.com,1999:blog-5608594534633161456.post-14862870606548086972011-02-21T09:43:42.805+05:302011-02-21T09:43:42.805+05:30Viraj Turakhia - ofcourse it is not possible with ...Viraj Turakhia - ofcourse it is not possible with just one tree traversal.. that is, unique tree contruction<br /><br />it is not even possible with two traversals in some cases<br /><br />for example:<br />post-order: aaaaaaaa<br />pre-order: aaaaaaaa<br />go construct a unique tree<br /><br />Bhavin Shah - @Vraj<br />1. lets assume input does not contain duplicate<br />2. jsut to clarify, I always meant both post-order and pre-order are given<br /><br />Viraj Turakhia - w/o duplicates, it should be possible to construct unique tree with any two traversals.<br />don't ask for algo.. can't write it here<br /><br />Bhavin Shah - nope its not possible if you have just post-order and pre-order traversals of binary tree.<br />consider following input:<br />pre-order: ab<br />post-order: ba<br /><br />you need two traversals and one of them has to be in-order.<br /><br />Viraj Turakhia - a is root and b is the only child.. tht's unique representation.. why u think it is not possible?<br /><br />Bhavin Shah - which child...left or right?<br /><br />Viraj Turakhia - thts non-deterministic even wen u draw this tree on paper.. :)<br /><br />Bhavin Shah - @Sagar told me both of them are correct answers.<br />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.Bhavin Shahhttps://www.blogger.com/profile/16257384637763382553noreply@blogger.com