Postorder Traversal Sequence of a Binary Search Tree

1. Problem Description

Given an integer array, determine whether it is the postorder traversal result of a binary search tree. Return true if it is, otherwise return false. Assume that any two numbers in the input array are distinct.

2. Approach

• The last element is the root. Split the sequence into two halves and ensure the left half is <= root and the right half is > root

3. Implementation

func VerifySquenceOfBST(sequence []int) bool {
	left := 0
	right := len(sequence) - 1
	return verifySquenceOfBST(sequence, left, right)

}

// Left-closed and right-closed
func verifySquenceOfBST(sequence []int, left int, right int) bool {
	if left >= right {
		return true
	}
	// Use the last node (the root) to divide the array into two parts: the left part < root and the right part > root.
	root := sequence[right]
	var mid int
	for mid = left; mid < right; mid++ {
		if sequence[mid] > root {
			break
		}
	}
	// Verify that the right part is entirely > root; otherwise return false
	for i := mid; i < right; i++ {
		if sequence[i] <= root {
			return false
		}
	}
	// Recursively process the left and right parts
	return verifySquenceOfBST(sequence, left, mid-1) && verifySquenceOfBST(sequence, mid, right-1)
}

4. References

• Postorder Traversal Sequence of a Binary Search Tree - NowCoder