# Reconstructing a tree from its preorder and postorder lists

algorithmlanguage-agnosticreferencetraversaltree

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.

#### Best Solution

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.