reconstructing a tree from its preorder and postorder lists.
- by NomeN
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.