Take the 2-minute tour ×

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.

share|improve this question
I'm pretty sure it's possible with inorder and preorder/postorder but I don't think it's possible with preorder and postorder. With only a single list, I'm certain it's not possible. –  LeakyCode Jul 16 '09 at 11:44
The nodes must be unique, right? Cause otherwise you cannot distinguish e.g. (a, [(a, [(a, [])]), (a, [])]) and (a, [(a, []), (a, [(a, [])])]). –  Stephan202 Jul 16 '09 at 11:50
I think you need to clarify that you're talking about trees where a node may have an arbitrary number of children. Often, trees are defined so that each node has exactly two children and either or both of these may be "empty". In this case, it is not possible to reconstruct the tree from preorder and postorder because you can't tell whether a single child is the "left child" or "right child" (see discussion here: profile.iiita.ac.in/pkmallick_03/pages/3_16.html). –  Martin B Jul 16 '09 at 11:58
@Mehrdad I believe I've read that inorder is nonsensical for non-binary trees. –  NomeN Jul 16 '09 at 11:58
@Stephan of course nodes are unique. –  NomeN Jul 16 '09 at 12:00
show 5 more comments

5 Answers

up vote 5 down vote accepted

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:

  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:


share|improve this answer
My solution is very similar, however I am looking for a proven algorithm. If there is none, I might try to prove my algorithm by SO. If even the whole SO community can not prove it wrong it must be right...right? –  NomeN Jul 16 '09 at 12:11
If the whole SO community can not prove it wrong then it MIGHT be right :P –  AlbertoPL Jul 16 '09 at 12:19
I say code this one, and try it with as many trees as you can, however I believe it to be mathematically sound, I'm just no good at starting off proofs from scratch. –  AlbertoPL Jul 16 '09 at 12:20
Me neither, therefore the question...and it saves a hell of a lot of time even if I was proficient in writing proofs. –  NomeN Jul 16 '09 at 12:37
While it's not what you needed, here's a free version of the first article -- ntur.lib.ntu.edu.tw/bitstream/246246/2007041910032125/1/… –  Richard Dunlap Jul 16 '09 at 20:10
show 5 more comments

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.

   / \
  2   1
     / \
    3   6

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

share|improve this answer
Ah ... but I do not care about left or right children, only about the order of the siblings. I will edit my question. +1 for the source though. –  NomeN Jul 16 '09 at 12:06
add comment

Consider an arbitrary tree T as the quadruple (A, B, C, D), where A is the root node, B is the root node of the first child, C is a vector of any non-empty children of B, and D is a vector of any non-empty siblings of B. The elements of C and D are themselves trees.

Any of A, B, C and D may be empty. If B is empty, so must be C and D; if A, then everything.

Since nodes are unique, the sets of nodes contained anywhere within C and D are disjoint, and neither contains A or B.

Functions pre() and post() generate ordered sequences of the form:

pre(T) = [A, B, pre(C), pre(D)]

post(T) = [post(C), B, post(D), A]

where the function applied to a vector is defined to be the concatenation of the sequences resulting from applying the function to each element in turn.

Now consider the cases:

  • if A is empty, the output of both functions is the empty sequence []
  • if B is empty, the output of both functions is just [A]
  • if C and D are empty, pre(T) = [A, B] and post(T) = [B, A]
  • if just C is empty, pre(T) = [A, B, D'] and post(T) = [B, D'', A] (where the primes indicate some permutation of the nodes contained within D)
  • if just D is empty, pre(T) = [A, B, C'] and post(T) = [C'', B, A]
  • if none are empty, pre(T) = [A, B, C', D'] and post(T) = [C'', B, D'', A]

In all cases we can unambiguously partition the members of the two output sequences into the appropriate subsequences, by using A and B (if present) as delimiters.

The question then is, can we also partition the vector sequences? If we can, then each can be recursively processed and we're done.

Since the result of pre() will always be a chain of sequences starting with A nodes, and the result of post() will always be a chain of sequences ending with A nodes, we can indeed divide them up, provided that the A nodes are never empty.

This is where the process falls down in the case of binary (or indeed any) trees with fixed children that may independently be empty. In our case, however, we have defined C and D to contain only non-empty nodes, and so the reconstruction is guaranteed to work.

Um, I think so, anyway. Obviously this is just an argument, not a formal proof!

share|improve this answer
I believe you came up with the exact same algorithm as I had in my mind, I eventually turned it into a little paper because I could not find any quotable resource. The principle idea being that you can recursively reconstruct the tree due to the position of the root of the (sub)tree in the pre and post respectively, all children will lie between those positions. The first child is then the leftmost of those nodes in pre, the second is the leftmost node that isnt a child of the first etc... –  NomeN Apr 22 '10 at 19:31
And your efforts are very much appreciated, but I have to say... necromancy much? (+1 anyway) –  NomeN Apr 22 '10 at 19:32
Just happened to be on the front page when I dropped in (thanks to komal's non-answer, I guess) and piqued my interest. How about posting a link to your paper for future reference? –  walkytalky Apr 22 '10 at 20:25
add comment

Create a binary tree with this restriction that has at least one node that this node has only one child(right or left ,there is no difference).

Now, write its Preorder and Postorder lists. then try to reconstructing the tree from these lists. and you realize that on that node you cannot decide that its child is right or left.

share|improve this answer
First off, pretty cool that there are still additions after all this time! For the binary tree the algorithm can be copied from TAOCP, however, the given tree will not be binary (or won't have been ;-)), so I am afraid that is out of the window for this problem. –  NomeN Jan 4 '12 at 10:54
all right , but you can to generalize my answer to any other tree( not specially a binary tree, the binary tree is the simplest tree that you can do the instruction about it),Try ! I know you can! ;-)))) –  Maryam A Jan 10 '12 at 17:12
In "Note4" the questioner mentions he doesn't care about left-vs-right in the case of only one child. –  danfuzz Nov 3 '12 at 3:22
add comment

The preorder and postorder traversals are sufficient to reconstruct the tree, assuming the nodes are uniquely named. The key to creating the algorithms to do so is to understand that

X is an ancestor of Y iff X precedes Y in the preorder and is after Y in the postorder.

Given this, we can always find all the descendants of any node. The descendants of X always immediately follow X in the preorder, and precede X in the postorder. So once we know we're interested in producing the subtree rooted at X, we can extract the preorder and postorder traversal for the subtree rooted at X. This leads naturally to a recursive algorithm, once we realize that the node immediately after X must be its leftmost child, if it is a descendant at all.

There is also a stack-based implementation, which iterates through the preorder nodes, and keeps on the stack any nodes which are candidates to be the direct parent of the next preorder node. For each preorder node, repeatedly pop all nodes off the stack which are not parents of the next preorder node. Make that node a child of the top node on the stack, and push the child onto the stack.

share|improve this answer
add comment

Your Answer


