Which combinations of pre-, post- and in-order sequentialisation are unique?

Question Detail: 

We know post-order,

post L(x)     => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] 

and pre-order

pre L(x)     => [x] pre N(x,l,r) => [x] ++ (pre l) ++ (pre r) 

and in-order traversal resp. sequentialisation.

in L(x)     => [x] in N(x,l,r) => (in l) ++ [x] ++ (in r) 

One can easily see that neither describes a given tree uniquely, even if we assume pairwise distinct keys/labels.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.

Asked By : Raphael

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/439

Answered By : Gilles

First, I'll assume that all elements are distinct. No amount of sequentialisations is going to tell you the shape of a tree with elements [3,3,3,3,3]. It is possible to reconstruct some trees with duplicate elements, of course; I don't know what nice sufficient conditions exist.

Continuing on the negative results, you can't fully rebuild a binary tree from its pre-order and post-order sequentializations alone. [1,2] preorder, [2,1] post-order has to have 1 at the root, but 2 can be either the left child or the right child. If you don't care about this ambiguity, you can reconstruct the tree with the following algorithm:

• Let $[x_1,\dots,x_n]$ be the pre-order traversal and $[y_n,\ldots,y_1]$ be the post-order traversal. We must have $x_1=y_1$, and this is the root of the tree.
• $x_2$ is the leftmost child of the root, and $y_2$ is the rightmost child. If $x_2 = y_2$, the root node is unary; recurse over $[x_2,\ldots,x_n]$ and $[y_n,\ldots,y_2]$ to build the single subtree.
• Otherwise, let $i$ and $j$ be the indices such that $x_2 = y_i$ and $y_2 = x_j$. $[x_2,\ldots,x_{j-1}]$ is the pre-order traversal of the left subtree, $[x_j,\ldots,x_n]$ that of the right subtree, and similarly for the post-order traversals. The left subtree has $j-2=n-i+1$ elements, and the right subtree has $i-2=n-j+1$ elements. Recurse once for each subtree.
  By the way, this method generalizes to trees with arbitrary branching. With arbitrary branching, find out the extent of the left subtree and cut off its $j-2$ elements from both lists, then repeat to cut off the second subtree from the left, and so on.

As stated, the running time is $O(n^2)$ with $\Theta(n^2)$ worst case (in the case with two children, we search each list lineraly). You can turn that into $O(n\,\mathrm{lg}(n))$ if you preprocess the lists to build an $n\,\mathrm{lg}(n)$ finite map structure from element values to positions in the input lists. Also use an array or finite map to go from indices to values; stick to global indices, so that recursive calls will receive the whole maps and take a range as argument to know what to act on.

With the pre-order traversal $[x_1,\ldots,x_n]$ and the in-order traversal $[z_1,\ldots,z_n]$, you can rebuild the tree as follows:

• The root is the head of the pre-order traversal $x_1$.
• Let $k$ be the index such that $z_k = x_1$. Then $[z_1,\ldots,z_{k-1}]$ is the in-order traversal of the left child and $[z_{k+1},\ldots,z_n]$ is the in-order traversal of the right child. Going by the number of elements, $[x_2,\ldots,x_k]$ is the pre-order traversal of the left child and $[x_{k+1},\ldots,x_n]$ that of the right child. Recurse to build the left and right subtrees.

Again, this algorithm is $O(n^2)$ as stated, and can be performed in $O(n\,\mathrm{lg}(n))$ if the list is preprocessed into a finite map from values to positions.

Post-order plus in-order is of course symmetric.