Constructing preorder traversal from postorder of a Binary Search Tree in O(n)

We are given postorder traversal of a Binary "SEARCH" Tree (in an array) and we want to find (print) its preorder traversal.

A very naive solution is to check from end until we find element less than root so we can find left and right subtree and call the function on them. This is $$O(n^2)$$. Another way is to generate the BST from its postorder and then generate the preorder from postorder. it is $$O(n log n)$$ because for generating tree we need $$O(n log n)$$ and for preorder traversal we need $$O(n)$$ and $$O(n + n log n ) = O(n logn)$$.

I think we can do it better in $$O(n)$$ because there is a lot known about the nature of the binary search tree and this extra information must help somehow. but I don't know how to use information we know about BST and implement this problem in $$O(n)$$.

• Can you help me make the connection between title (conversion between traversals) and body (find key given postorder) of your question? Nov 24, 2019 at 12:17
• @greybeard I didn't say anything about key. In the body, I said we want to find where is left and where is right subtree and run the function recursively on them. The other answer is just generating the BST from preorder and then finding postorder traversal. But these ways are not efficient. There must be $O(n)$ solution for this. My question is simply about how to convert postorder traversal to preorder traversal in $O(n)$. (it is on a BST so preorder and postorder are unique) Nov 24, 2019 at 15:15
• I have read find (print) as trying to find as a key the string print Nov 24, 2019 at 15:30
• for [re-]generating [the] tree we need $O(nlogn)$ [time] I'd like to challenge that this bound is tight (and claim $O(n)$). Fast in $\omicron(n)$ memory sounds a challenge. Nov 24, 2019 at 16:34

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.

• (You don't need to use the actual min and max value.) Nov 24, 2019 at 18:10