# Post-order Traversal Sequences of Binary Search Trees

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.
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.
every left and right part need to be “true”.
boolean 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);

}