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?
Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound
algorithms;binary trees;lower bounds