# Verify Post-order Sequence of Binary Search Tree

## 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.

## Pseudocode

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

## Sample

```
class Node:
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)
return front == node.value
node_5 = Node(5)
node_7 = Node(7)
node_9 = Node(9)
node_11 = Node(11)
node_6 = Node(6, node_5, node_7)
node_10 = Node(10, node_9, node_11)
node_8 = 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) # True
print postorder(root, test_seq_2) # False
```