Subscribe to:
Post Comments (Atom)
skip to main |
skip to sidebar
About Me
- Bhavin Shah
- People who know me, know me...others why bother, enjoy a good read and post healthy comments :-)
Viraj Turakhia - ofcourse it is not possible with just one tree traversal.. that is, unique tree contruction
ReplyDeleteit is not even possible with two traversals in some cases
for example:
post-order: aaaaaaaa
pre-order: aaaaaaaa
go construct a unique tree
Bhavin Shah - @Vraj
1. lets assume input does not contain duplicate
2. jsut to clarify, I always meant both post-order and pre-order are given
Viraj 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 here
Bhavin Shah - nope its not possible if you have just post-order and pre-order traversals of binary tree.
consider following input:
pre-order: ab
post-order: ba
you 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
ReplyDeleteWhere small letters are leaf node
ReplyDeleteCapital letters are intermediate and root node