You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Verify Post-order Sequence of Binary Search Tree

Nicholas Wong
Nicholas Wong

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

Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.