Is there a way to find the pre order traversal of a strictly binary tree from its post order traversal without building the tree? [closed]

Question

I am given a post order traversal of a strictly binary tree and am asked to find the pre order traversal of it. Normally, I would go a build the tree first, then find the pre order traversal. But, I was wondering if there was any way to find the pre order traversal without actually building the tree.

Answer 1

[Edit: I first answered the question under the assumption the the given post-order was from a binary search tree with strict ordering. OP has now pointed out my error and provided an example. The basic principle of both algorithms is the same, however: Find where the boundary between the left and right subtrees is.]

Let's consider the following post-order traversal of a full binary tree where every node is either a leaf or a branch with two leaves:

1, 2, B, 3, 4, D, 5, C, A

We know that numbers are leaves and letters are branches. We also know that node A is the root, because it comes last in the post-order traversal. In order to reconstruct the pre-order traversal, we must store the root, then consider the left subtree, then the right subtree recursively.

But which nodes belong to the left, which to the right subtree? In a full or strictly binary tree with L leaves, there are N = 2·L − 1 nodes. So after storing the root, we travel the remaining subarray from the right and keep track of the number of nodes N and the number of leaves L. When the considtion N = 2·L − 1 is true, we stop. Everything we've seen belongs to the right subtree, the rest belongs to the left subtree.

So:

int is_leaf(int c)
{
    return !isalpha(c);     // non-alphas are leaves
}

void reconst(int **pre, const int *post, int lo, int hi)
{
    printf("%d :: %d\n", lo, hi);

    if (lo < hi) {
        int k = --hi;           // will be boundary between l/r
        int root = post[k];
        int leaves = 0;
        int nodes = 0;

        while (k > lo && nodes != 2 * leaves - 1) {
            if (is_leaf(post[k - 1])) leaves++;
            nodes++;
            k--;
        }

        *(*pre)++ = root;
        reconst(pre, post, lo, k);
        reconst(pre, post, k, hi);
    }
}

Call it like this:

int post[] = {'1', '2', 'B', '3', '4', 'D', '5', 'C', 'A'};
int n = 9;
int pre[9];
int *p = pre;
int i;

reconst(&p, post, 0, n);

for (i = 0; i < n; i++) {
    printf("%c ", pre[i]);
}

puts("pre");

The code above relies on several things: (a) The prearray must be as big as the post array to hold the reconstructed pre-order. (b) The input must be well formed. The algorithm relies on finding a correct full subtree. (The counter is guarded against walking beyond the lower bound, but that's about it.)

---

[Original post that tries to find the pre-order from the post-order of a binary search tree without duplicate value, i.e. with strict ordering. Nice answer, but because misunderstood the requirements, not what OP wanted. Sorry about that.]

Say you get a post-order traversal like this:

3, 1, 7, 9, 8, 5

You know that the top node is (5) and that all smaller nodes (3, 1) are in the left branch and all larger nodes (7, 8, 9) are in the right branch. The top node goes in first in pre-order traversal. Do that, then recurse on the subarray that represents the left branch, then the right branch.

Here's a function that does that:

void reconst(int **pre, const int *post, int lo, int hi)
{
    if (lo < hi) {
        int k = --hi;                // k will be the boundary between l/r
        int parent = post[k];        // remove parent from this subarray

        // find boundary between left and right branches
        while (k > lo && post[k - 1] > parent) k--;

        *(*pre)++ = parent;          // write parent to pre-order array
        reconst(pre, post, lo, k);   // do the left subarray
        reconst(pre, post, k, hi);   // do the right subarray
    }
}

The pre array is filled via a pointer to a pointer: The top level pointer keeps track of the osition in the pre array, the second-level pointer accesses the underlying array. (You can pass an array an an index, which you can advance instead, if that's too baroque.)

Call the function like this:

int post[] = {3, 1, 7, 9, 8, 5};
int n = 6;
int pre[6];
int *p = pre;
int i;

reconst(&p, post, 0, n);

for (i = 0; i < n; i++) {
    printf("%d ", pre[i]);
}

puts("pre");

Of course, the array to hold the pre-order data must be as big as the post-order array. Code that rebuilds the tree from post-oder data would look very similar, so I don't know whether this really qualifies.