Can one extract the in-order given pre- and post-order for a binary search tree over < with only O(n) <-comparisons?

Question

Assume one has a binary search tree B, which is not necessarily balanced, over some domain D with the strict order relation < and n elements.

Given B's extracted pre-order R, post-order T:

1. Is it possible to compute B's in-order S in O(n) without access to <?
2. Is it possible to compute B's in-order S using only O(n) comparisons with <?
3. Furthermore is it possible to compute S in O(n) total?

---

_{Note: This is a re-post of a now-deleted unanswered question.}

Answer 1

1. In-order without relation <

This is impossible as explained in Why it is impossible to construct Binary Tree with Pre-Order, Post Order and Level Order traversals given?. In short, the input R = cba, T = abc is ambiguous and could stem from both these trees:

    a      a
  /          \
b              b
 \            /
  c          c
S = bca   S = acb

2. In-order in O(n) comparisons

Using the < relation, one can suddenly differentiate trees like the above although the produce the same pre-order R and post-order T. Given:

R = Ca

with C some arbitrary non-empty range of a's children nodes with C = u...v (i.e. range starts with u and ends with v) one can infer the following:

 (1) a < u        -> a has 1 direct child (to its right) -> all children are greater than a
 (2) v < a        -> a has 1 direct child (to its left)  -> all children are less than a
 (3) otherwise    -> a has 2 direct children

Recursion in (1) and (2) is trivial and we have spent O(1) <. In case of (3) we have something of the form:

 R = XbYca
 T = abXcY

where X and Y are arbitrary sequences. We can split this into the recursion steps:

             R = XbYca
             T = abXcY
          /             \
 R = Xb                     R = Yc
 T = bX                     T = cY

Note that this requires no comparisons with <, but requires to split both ranges. Since X and Y need not be the same length, finding the splitting-point requires us to find b in R, which can be done in O(n) for each level of the recursion tree. So in total we need O(n*d) equality comparisons, where d is the depth of the original binary search tree B (and the recursion tree which mirrors B).

In each recursion step we use at most 2 < comparisons, getting out one element of the range, hence we cannot use more than 2*n < comparisons (which is in O(n)).

3. In-order in O(n) total

In the algorithm given above the problem is that finding the point where to split the range containing all children cannot be done better than in linear time if one cannot afford a lookup table for all elements.

But, if the universe over which B is defined is small enough to be able to create an index table for all entries, one can pre-parse R (e.g. R = xbyca) in O(n) and create a table like this:

a -> 4
b -> 1
c -> 3
d -> N/A
e -> N/A
....
x -> 0
y -> 2
z -> N/A

Only if this is feasible one can achieve overall O(n) with the algorithm described in 2. It consume O(2^D) space.

Is it otherwise possible to produce the in-order S in O(n).

I don't have a proof for this, but do not think it is possible. The rationale is that the problem is too similar to comparison sorting which cannot be better than linearythmic.

In "2." we get away with linear comparisons because we can exploit the structure of the input in conjunction with a lot of equality checks to partially reconstruct the original structure of the binary search tree at least locally. However, I don't see how the size of each sub-tree can be extracted in less than linear time.