Interview Practice 09 - Verify Post-order Sequence of BST

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); }