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

Question

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)$.

Answer 1

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.