figure out the structure of a binary search tree given preorder traversal

Question

Hi I am struggling to figure this out. The pre-order traversal of a binary search tree is: 15, 9, 6, 1, 7, 13, 23, 19, 39, 32.

what would be the postorder traversal of it?

to figure out the post order traversal, we need to obtain the structure of the binary tree first, but I am struggling to figure this out.

Thanks

Answer 1

As the input is a preorder traversal, we can insert the values into a (growing) BST as leaves in that order:

• They would need to be leaves at the moment of insertion, as otherwise they would be a parent of an earlier inserted node, which is in contradiction with the preorder sequence of the input.

• In a binary search tree there is only one spot to add a new value as a leaf.

Following the above observations, you can just insert the values into a BST in the order you read them from the input, using the usual insertion algorithm.

But actually building the binary search tree is not necessary. We can derive the post order traversal from the input using a stack, or an (equivalent) recursive procedure.

The main idea is that the preorder values arrive below a node as long as its values are not crossing a maximum value -- a maximum that is determined by an ancestor node's value where we currently are in the left subtree of that ancestor. So by the use of a stack (or recursion) we can output that subtree in a bottom up fashion (postorder).

Here is an implementation:

#include <stdio.h>
#include <limits.h>

void dfsHelper(int preOrder[], int n, int *i, int high, int postOrder[], int *j) {
    if (*i >= n) return;
    int value = preOrder[*i];
    if (value > high) return;
    (*i)++;
    dfsHelper(preOrder, n, i, value, postOrder, j); // Output left subtree
    dfsHelper(preOrder, n, i, high, postOrder, j);  // Output right subtree
    postOrder[(*j)++] = value;                      // Output node
}

void preToPostOrder(int preOrder[], int n, int postOrder[]) {
    int i = 0, j = 0;
    dfsHelper(preOrder, n, &i, INT_MAX, postOrder, &j);
}

int main() {
    // Example input as given in the question:
    int preOrder[] = {15, 9, 6, 1, 7, 13, 23, 19, 39, 32};
    int n = sizeof(preOrder) / sizeof(int);
    int postOrder[n]; // Target for the output of this algorithm
    preToPostOrder(preOrder, n, postOrder);
    // Output post order result
    for (int i = 0; i < n; i++) printf("%d ", postOrder[i]);
    printf("\n");
    return 0;
}