How to construct a tree given its depth and postorder traversal, then print its preorder traversal

Question

I need to construct a tree given its depth and postorder traversal, and then I need to generate the corresponding preorder traversal. Example:

Depth: 2 1 3 3 3 2 2 1 1 0
Postorder: 5 2 8 9 10 6 7 3 4 1
Preorder(output): 1 2 5 3 6 8 9 10 7 4

I've defined two arrays that contain the postorder sequence and depth. After that, I couldn't come up with an algorithm to solve it.

Here's my code:

int postorder[1000];
int depth[1000];
string postorder_nums;
getline(cin, postorder_nums);
istringstream token1(postorder_nums);
string tokenString1;
int idx1 = 0;
while (token1 >> tokenString1) {
    postorder[idx1] = stoi(tokenString1);
    idx1++;
}
string depth_nums;
getline(cin, depth_nums);
istringstream token2(depth_nums);
string tokenString2;
int idx2 = 0;
while (token2 >> tokenString2) {
    depth[idx2] = stoi(tokenString2);
    idx2++;
}
Tree tree(1);

Answer 1

You can do this actually without constructing a tree.

First note that if you reverse the postorder sequence, you get a kind of preorder sequence, but with the children visited in opposite order. So we'll use this fact and iterate over the given arrays from back to front, and we will also store values in the output from back to front. This way at least the order of siblings will come out right.

The first value we get from the input will thus always be the root value. Obviously we cannot store this value at the end of the output array, as it really should come first. But we will put this value on a stack until all other values have been processed. The same will happen for any value that is followed by a "deeper" value (again: we are processing the input in reversed order). But as soon as we find a value that is not deeper, we flush a part of the stack into the output array (also filling it up from back to front).

When all values have been processed, we just need to flush the remaining values from the stack into the output array.

Now, we can optimise our space usage here: as we fill the output array from the back, we have free space at its front to use as the stack space for this algorithm. This has as nice consequence that when we arrive at the end we don't need to flush the stack anymore, because it is already there in the output, with every value where it should be.

Here is the code for this algorithm where I did not include the input collection, which apparently you already have working:

// Input example
int depth[] = {2, 1, 3, 3, 3, 2, 2, 1, 1, 0};
int postorder[] = {5, 2, 8, 9, 10, 6, 7, 3, 4, 1};
// Number of values in the input
int n = sizeof(depth)/sizeof(int);

int preorder[n]; // This will contain the ouput
int j = n; // index where last value was stored in preorder
int stackSize = 0; // how many entries are used as stack in preorder
for (int i = n - 1; i >= 0; i--) {
    while (depth[i] < stackSize) {
        preorder[--j] = preorder[--stackSize]; // flush it
    }
    preorder[stackSize++] = postorder[i]; // stack it
}
// Output the result:
for (int i = 0; i < n; i++) {
    std::cout << preorder[i] << " ";
}
std::cout << "\n";

This algorithm has an auxiliary space complexity of O(1) -- so not counting the memory needed for the input and the output -- and has a time complexity of O(n).

Answer 2

I won't give you the code, but some hints how to solve the problem.

First, for postorder graph processing you first visit the children, then print (process) the value of the node. So, the tree or subtree parent is the last thing that is processed in its (sub)tree. I replace 10 with 0 for better indentation:

2 1 3 3 3 2 2 1 1 0
--------------------
5 2 8 9 0 6 7 3 4 1

As explained above, node of depth 0, or the root, is the last one. Let's lower all other nodes 1 level down:

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
5 2 8 9 0 6 7 3 4 

Now identify all nodes of depth 1, and lower all that is not of depth 0 or 1:

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
  2           3 4 
5   8 9 0 6 7 

As you can see, (5,2) is in a subtree, (8,9,10,6,7,3) in another subtree, (4) is a single-node subtree. In other words, all that is to the left of 2 is its subtree, all to the right of 2 and to the left of 3 is in the subtree of 3, all between 3 and 4 is in the subtree of 4 (here: empty).

Now lets deal with depth 3 in a similar way:

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
  2           3 4 
5         6 7 
    8 9 0  

• 2 is the parent for 2;
• 6 is the parent for 8, 8, 10;
• 3 is ahe parent for 6,7;

or very explicitly:

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
   /           / /
  2           3 4 
 /         / /
5         6 7 
     / / /
    8 9 0  

This is how you can construct a tree from the data you have.

EDIT

Clearly, this problem can be solved easily by recursion. In each step you find the lowest depth, print the node, and call the same function recursively for each of its subtrees as its argument, where the subtree is defined by looking for current_depth + 1. If the depth is passed as another argument, it can save the necessity of computing the lowest depth.