Post-order Traversal Sequences of Binary Search Trees - Interview Question&Answer

Problem: Determine whether an input array is a post-order traversal sequence of a binary tree or not. If it is, return true; otherwise return false. Assume all numbers in an input array are unique.

For example, if the input array is {5, 7, 6, 9, 11, 10, 8}, true should be returned, since it is a post-order traversal sequence of the binary search tree in Figure 1. If the input array is {7, 4, 6, 5}, false should be returned since there are no binary search trees whose post-order traversal sequence is such an array.

Figure 1: A binary search tree with post-order traversal sequence {5, 7, 6, 9, 11, 10, 8}

Analysis: The last number is a post-order traversal sequence is the value of root node. Other numbers in a sequence can be partitioned into two parts: The left numbers, which are less than the value of root node, are value of nodes in left sub-tree; the following numbers, which are greater than the value of root node, are value of nodes in right sub-tree.

Take the input {5, 7, 6, 9, 11, 10, 8} as an example, the last number 8 in this sequence is value of root node. The first 3 numbers (5, 7 and 6), which are less than 8, are value of nodes in left sub-tree. The following 3 numbers (9, 11 and 10), which are greater than 8, are value of nodes in right sub-tree.

We can continue to construct the left sub-tree and right sub-tree according to the two sub-arrays with the same strategy. In the subsequence {5, 7, 6}, the last number 6 is the root value of the left sub-tree. The number 5 is the value of left child since it is less than root value 6, and 7 is the value of right child since it is greater than 6. Meanwhile, the last number 10 in subsequence {9, 11, 10} is the root value of right sub-tree. The number 9 is value of left child, and 11 is value of right child accordingly.

Let us analyze another array {7, 4, 6, 5}. The last number 5 is the value of root node. Since the first number 7 is greater than 5, there are no nodes in the left sub-tree and numbers 7, 4, 6 are all value of nodes in right sub-tree. However, we notice that a number 4, a value in right sub-tree, is less than the root value 5. It violates the definition of binary search trees. Therefore, there are no binary search trees with post-order traversal sequence {7, 4, 6, 5}.

It is not difficult to write code after we get the strategy above. Some sample code is shown below:

bool VerifySquenceOfBST(int sequence[], int length)

{

    if(sequence == NULL || length <= 0)

        return false;

    int root = sequence[length - 1];

    // nodes in left sub-tree are less than root node

    int i = 0;

    for(; i < length - 1; ++ i)

    {

        if(sequence[i] > root)

            break;

    }

    // nodes in right sub-tree are greater than root node

    int j = i;

    for(; j < length - 1; ++ j)

    {

        if(sequence[j] < root)

            return false;

    }

    // Is left sub-tree a binary search tree?

    bool left = true;

    if(i > 0)

        left = VerifySquenceOfBST(sequence, i);

    // Is right sub-tree a binary search tree?

    bool right = true;

    if(i < length - 1)

        right = VerifySquenceOfBST(sequence + i, length - i - 1);

    return (left && right);

}