Search code examples
algorithmtreepreorderpostorder

Rebuild a tree from pre-order and post-order traversals

Given the preorder and postorder traversals of a non-binary tree with unique elements how I create the tree they came from?

for example

given preorder = ABCDEF
and postorder = BCEFDA

it should build a tree equivalent to
~~A~~~~~
~/~|~\~~~
B~C~D~~
~~~~/~\~~
~~~E~~F~

(sorry about the tilde's, it was the only way i could figure out how to get the tree to look right and still be legible)

anyway, i'm not asking for the code to do this as it is a homework project and the code itself isn't the problem. What I need help with is the algorithm to compare the two inputs such that they reliably create the proper tree

P.S. The given tree could be more or less complicated with any number (presumably <= 26) of nodes

TL;DR
How do I use Pre-order and Post-order traversals to construct their original tree

Solution

  • Recursive + iterative solution

    each level processes entire string passed into it

    • if first elements are equal - remove and add as child of current level
    • if first elements not equal - remove first element pre order as parent and recursively call on substring of that to position where post order element was found

    call with empty sentinal as parent of A

    This will give you a result in MOST cases.