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?


  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.

  2. Can we construct a tree by the postorder txyCabDBA

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