title: reconstructing a tree from its preorder and postorder lists
body: <p>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. </p>
  
  <p>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?)</p>
  
  <p>In short, I need a proven algorithm in a quotable resource that reconstructs a tree from its pre and post order traversals.</p>
  
  <hr>
  
  <p>Note: The tree in question will probably not be binary, or balanced, or anything that would make it too easy.</p>
  
  <p>Note2: Using only the preorder or the postorder list would be even better, but I do not think it is possible.</p>
  
  <p>Note3: A node can have any amount of children.</p>
  
  <p>Note4: I only care about the order of siblings. Left or right does not matter when there is only one child.</p>