Friday, February 18, 2011

Construct binary tree using Post-order and Pre-order Traversals

Is it possible to build a binary tree given only Post-order and Pre-order traversals of that tree?

3 comments:

  1. Viraj Turakhia - ofcourse it is not possible with just one tree traversal.. that is, unique tree contruction

    it 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.

    ReplyDelete
  2. Can we construct a tree by the postorder txyCabDBA

    ReplyDelete
  3. Where small letters are leaf node
    Capital letters are intermediate and root node

    ReplyDelete