### Question

Construct an algorithm to verify if a set of numbers is the post-order search result of a binary search tree. Let the figure at the right hand side as an example, the algorithm will return true if {5, 7, 6, 9, 11, 10, 8}. However, it will return false if the input is {7, 4, 6, 5}.

### Solution

Actually, a post-order search of the whole tree would do the job. First, perform a depth-first search from the leftmost leave, and push each element into a stack.

Wikipedia

### Pseudocode

```postorder(node)
if node == null then return
postorder(node.left)
postorder(node.right)
visit(node)```

### Samples

```class bst_node:
value = None
left = None
right = None
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

def postorder(node, test_seq):
if node is None: return True
if not postorder(node.left, test_seq): return False
if not postorder(node.right, test_seq): return False
return visit(node, test_seq)

def visit(node, test_seq):
front = test_seq.pop(0) # front item
return front == node.value

node_5 = bst_node(5)
node_7 = bst_node(7)
node_9 = bst_node(9)
node_11 = bst_node(11)
node_6 = bst_node(6, node_5, node_7)
node_10 = bst_node(10, node_9, node_11)
node_8 = bst_node(8, node_6, node_10)
root = node_8

test_seq_1 = [5, 7, 6, 9, 11, 10, 8]
test_seq_2 = [7, 4, 6, 5]

print postorder(root, test_seq_1)
print postorder(root, test_seq_2)```
```bool verifySquenceOfBST(int squence[], int length)
{
if(squence == NULL || length <= 0)
return false;

// root of a BST is at the end of post order traversal squence
int root = squence[length - 1];

// the nodes in left sub-tree are less than the root
int i = 0;
for(; i < length - 1; ++ i)
{
if(squence[i] > root)
break;
}

// the nodes in the right sub-tree are greater than the root
int j = i;
for(; j < length - 1; ++ j)
{
if(squence[j] < root)
return false;
}

// verify whether the left sub-tree is a BST
bool left = true;
if(i > 0)
left = verifySquenceOfBST(squence, i);

// verify whether the right sub-tree is a BST
bool right = true;
if(i < length - 1)
right = verifySquenceOfBST(squence + i, length - i - 1);

return (left && right);
}```