algorithm - reconstructing a tree from its preorder and postorder lists

Question

Consider the situation where you have two lists of nodes of which all you know is that one is a representation of a preorder traversal of some tree and the other a representation of a postorder traversal of the same tree.

I believe it is possible to reconstruct the tree exactly from these two lists, and I think I have an algorithm to do it, but have not proven it. As this will be a part of a masters project I need to be absolutely certain that it is possible and correct (Mathematically proven). However it will not be the focus of the project, so I was wondering if there is a source out there (i.e. paper or book) I could quote for the proof. (Maybe in TAOCP? anybody know the section possibly?)

In short, I need a proven algorithm in a quotable resource that reconstructs a tree from its pre and post order traversals.

---

Note: The tree in question will probably not be binary, or balanced, or anything that would make it too easy.

Note2: Using only the preorder or the postorder list would be even better, but I do not think it is possible.

Note3: A node can have any amount of children.

Note4: I only care about the order of siblings. Left or right does not matter when there is only one child.

Answer 1

Preorder and postorder do not uniquely define a tree.

In general, a single tree traversal does not uniquely define the structure of the tree. For example, as we have seen, for both the following trees, an inorder traversal yields [1,2,3,4,5,6].

    4                     3
   /                    / 
  2   5                 2   5
 /                   /   / 
1   3   6             1   4   6

The same ambiguity is present for preorder and postorder traversals. The preorder traversal for the first tree above is [4,2,1,3,5,6]. Here is a different tree with the same preorder traversal.

    4
   / 
  2   1
     / 
    3   6
     
      5

Similarly, we can easily construct another tree whose postorder traversal [1,3,2,6,5,4] matches that of the first tree above.