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?

  • $\begingroup$ There is definitely no $\Omega(n^2)$ lower bound, since we don't know how to prove meaningful lower bounds on general computational models. $\endgroup$ – Yuval Filmus Jun 16 '17 at 11:21
  • $\begingroup$ My guess is that you should be able to do this in $O(n\log n)$, but it's just a guess. $\endgroup$ – Yuval Filmus Jun 16 '17 at 11:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Evil Jun 16 '17 at 11:26
  • $\begingroup$ @Evil Using binary search is a really good idea, thanks! $\endgroup$ – Karegar Jun 16 '17 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.