Is it possible to create a binary non-unique tree using the preorder and postorder sequences?

Is it possible to create a binary non-unique tree using the preorder and postorder sequences ?

If so, how can this be done ? For example how could I make a non-unique tree for:

Preorder:

B C I J K H D E F G

Postorder:

I H K J C G开发者_运维技巧 F E D B

How many could there be ?

---

preorder psedo-code:

preorder (tree)
{
    if tree isn't empty then
    {
        print key[tree]
        preorder left[tree]
        preorder right[tree]
    }
}

and post order is:

postorder (tree)
{
    if tree isn't empty then
    {
        preorder left[tree]
        preorder right[tree]
        print key[tree]
    }
}

so from inorder order we can conclude:

• "B" must be the root
• "C" must be "B"'s child
• "G" must be the the max value (the most far right node in the tree) or the min value in the left sub-tree (the most far left node in the left sub-tree) - in that case "G" must be a leaf and "F" must be "G"'s parent

and from postorder order we can conclude:

• "I" must be a leaf and the min value (the most right node in the tree).
• "H" must be "I"'s parent ("I" is "H" left child) in case I has no children, else "H" is the next far left child in the tree.

from here it's like a Sudoku:

and yes: by using preorder and postorder outputs you can build a tree in only one way.

---

Yes, it is possible to construct different binary trees that have the same pre- and postorder sequences. To generate such different trees, look for subtrees where either the left or the right child is empty and simply swap the children.

This minimal example

  a         a
 /    vs.    \
b             b

shows two trees that both have the preordering a b and the postordering b a.