This can indeed be solved in $O(n)$ time. What you mentioned (checking value of root, calling recursively for left and right subtree) almost works, the issue is just that we don't know the size of the right subtree, so we cannot immediately recursively solve the left subtree as we don't know where it ends. But this is not an issue: Just recursively solve the right subtree first, then have that return the subtree's size.
The following C++ program should solve the problem in $O(n)$. Please note that while I tested a few inputs but there could be bugs, though the idea behind the algorithm works for sure.
#include <iostream>
#include <vector>
using namespace std;
// Finds preorder traversal of a subtree of a binary search tree given the postorder traversal
// res: Vector to write preorder traversal to
// postorder: Vector containing the postorder traversal
// j: Position in array to write last node in preorder traversal to
// hv: Maximum value of a node in this subtree
// lv: Minimum value of a node in this subtree
// b: Position where this subtree ends in the postorder traversal
// Returns size of the subtree called on
int preorder(int b, int lv, int hv, int j, const vector<int>& postorder, vector<int>& res) {
if (b < 0 || postorder[b] < lv || postorder[b] > hv) return 0;
int rs = preorder(b-1, postorder[b], hv, j, postorder, res); // Size of right subtree
int ls = preorder(b-1-rs, lv, postorder[b], j - rs, postorder, res); // Size of left subtree
res[j - ls - rs] = postorder[b];
return ls + rs + 1;
}
int main() {
int n; // Size of the tree
cin >> n;
vector<int> po(n); // Postorder
for (int i = 0; i < n; ++i) cin >> po[i];
int lv = po[0]; // Minimum value in the tree
int hv = po[0]; // Maximum value in the tree
for (int i = 0; i < n; ++i) {
lv = min(lv, po[i]);
hv = max(hv, po[i]);
}
vector<int> res(n); // Preorder
preorder(n-1, lv, hv, n-1, po, res);
for (auto v : res) cout << v << ' ';
cout << '\n';
}
This is clearly $O(n)$, since the function "preorder" gets called exactly once per node, and (outside recursive calls) does $O(1)$ work.
find (print)
as trying to find as a key the string print… $\endgroup$