# Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound

I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I could only find a $O(n^2)$ (worst case) algorithm for this problem, like this link.

So I'm wondering whether a $o(n^2)$ algorithm for this problem is found or the $\Omega(n^2)$ lower bound is proven or is finding a reachable lower bound an open problem?

• There is definitely no $\Omega(n^2)$ lower bound, since we don't know how to prove meaningful lower bounds on general computational models. – Yuval Filmus Jun 16 '17 at 11:21
• My guess is that you should be able to do this in $O(n\log n)$, but it's just a guess. – Yuval Filmus Jun 16 '17 at 11:22
• If you change the "search" function to use sorted data, it changes to $\mathcal O(n\log n)$. I think that exploiting a special linear sorting is not possible here. Anyway, the question should be self-contained. – Evil Jun 16 '17 at 11:26
• @Evil Using binary search is a really good idea, thanks! – Karegar Jun 16 '17 at 16:58