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.

Answer 2

You cannot use only one list, because you'll get no sense of the depth of the tree. Thus, you definitely require two or more lists.

Here's my attempt at a solution:

Use your preorder traversal as a means of knowing the ordering of the data. This makes sense because you know the first node is the top, and you know that data further to the left of the traversal belongs to the left of the tree, etc.

Your post order traversal can determine the depth of the tree. For example, let's say I have a structure like this:

      1   2   5   6  3 4  7  Where 2 is the parent of 3 and 4, and 5 is the parent of 7.  Preorder: 1 2 3 4 5 7 6 Postorder: 3 4 2 7 5 6 1 

We know we start with 1, because it is the first node in the preorder traversal. Then we look at the next number, 2. In the post order, because the number 2 comes BEFORE node 1, we know that 2 has to be a child of 1. Next we look at 3. 3 comes before 2, and thus 3 is a child of 2. 4 is before 2 but after 3, so we know 4 is a child of 2 but NOT a child of 3. Etc.

Now, this may not work if the nodes are not unique, but at the very least its a start to a solution.

Edit: The order of the children is preserved with this solution, simply due to knowing the ordering of the nodes via the preorder traversal, and then knowing the structure via the postorder traversal.

Edit2: The proof may lie here: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber%3D17225&authDecision=-203

I think you need to purchase the document, however...

Here is a written proof presented to be a solution:

http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf