Algorithm

Verify Post-order Sequence of Binary Search Tree

Nicholas Wong

Nicholas Wong

— 1 min read
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

Reference

Read more