Coding Interview Questions: No. 06 - Post-order Traversal Sequences of Binary Search Trees

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

Take examples and simulation.
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.

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);

        if(!left) return false;

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

    bool right = true;

    if(i < length - 1)

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

    return right;

}
Further Questions:
The number of ways to construct BST from Post-Order Sequence.
Read full article from Coding Interview Questions: No. 06 - Post-order Traversal Sequences of Binary Search Trees