Check if postordered array forms a binary search tree

Problem

Given an array representing a Postorder Traversal of a Binary Tree, determine whether the possible binary tree formed from it can qualify as a Binary Search Tree (BST).

A Binary Search Tree is defined as:

• For every node in the tree:
  • Left subtree nodes' values are less than the node's value.
  • Right subtree nodes' values are greater than the node's value.

Example

Problem

Examples

Example 1

Input: postorder = [2, 4, 3, 8, 7, 5]
Output: True
Explanation: This postorder traversal can form a valid Binary Search Tree:
		  5
		 / \
		3   7
	   / \    \
	  2   4    8

Example 2

Input: postorder = [1, 3, 2, 6, 5]
Output: False
Explanation: This postorder traversal cannot form any valid Binary Search Tree because 6 exists on the left side of 5, violating the BST property.

Solution

Method 1 - Using BST Property

The Postorder Traversal visits nodes in the following order:

1. Left Subtree
2. Right Subtree
3. Root Node

We can use the following observations while checking if the input array can be formed into a BST:

• The last element of the postorder traversal is always the root of the tree.
• Elements before the root should split into 2 sections:
  • Left subtree: Values less than the root.
  • Right subtree: Values greater than the root.
• Recursively validate the left and right subtrees to ensure they satisfy the BST constraints.

Approach

1. Start with the entire postorder array and treat the last element as the root.
2. Find the boundary between the values of the left subtree and the right subtree:
   • Values smaller than the root belong to the left subtree.
   • Values larger than the root belong to the right subtree.
3. Ensure no value in the left violates the BST property (greater than root), and no value in the right violates property (smaller than root).
4. Recursively repeat the process for the left and right subtrees.
5. If at any point an inconsistency is found, return False.

Code

Java

class Solution {

    public boolean isPostOrderBST(int[] postorder) {
        return isPostOrderBSTHelper(postorder, 0, postorder.length - 1);
    }

    private boolean isPostOrderBSTHelper(int[] postorder, int start, int end) {
        if (start >= end) {
            return true; // Single element or empty -> valid BST
        }

        // Last element is the root
        int root = postorder[end];
        int i = start;

        // Find boundary between left and right subtree
        while (i < end && postorder[i] < root) {
            i++;
        }

        // Verify that all elements in the 'right subtree' are greater than root
        for (int j = i; j < end; j++) {
            if (postorder[j] < root) {
                return false; // Violates BST property
            }
        }

        // Recursively check left and right subtrees
        return (
            isPostOrderBSTHelper(postorder, start, i - 1) &&
            isPostOrderBSTHelper(postorder, i, end - 1)
        );
    }

    // Main function for testing examples
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        int[] postorder1 = { 2, 4, 3, 8, 7, 5 };
        System.out.println(solution.isPostOrderBST(postorder1)); // Output: True

        // Example 2
        int[] postorder2 = { 1, 3, 2, 6, 5 };
        System.out.println(solution.isPostOrderBST(postorder2)); // Output: False
    }
}

Python

class Solution:
    def isPostOrderBST(self, postorder):
        def helper(start, end):
            if start >= end:
                return True  # Single element or empty -> valid BST
            
            # Last element is the root
            root = postorder[end]
            i = start
            
            # Find boundary between left and right subtree
            while i < end and postorder[i] < root:
                i += 1
            
            # Verify that all elements in the 'right subtree' are greater than root
            for j in range(i, end):
                if postorder[j] < root:
                    return False  # Violates BST property
            
            # Recursively check left and right subtrees
            return helper(start, i - 1) and helper(i, end - 1)
        
        # Trigger helper recursively
        return helper(0, len(postorder) - 1)

# Main function for testing examples
if __name__ == "__main__":
    solution = Solution()
    
    # Example 1
    postorder1 = [2, 4, 3, 8, 7, 5]
    print(solution.isPostOrderBST(postorder1))  # Output: True
    
    # Example 2
    postorder2 = [1, 3, 2, 6, 5]
    print(solution.isPostOrderBST(postorder2))  # Output: False

Complexity

• ⏰ Time complexity: O(n^2). In the worst case, every check requires scanning the entire subtree (n) for splitting into left and right sections. For n elements, the complexity is quadratic.
• 🧺 Space complexity: O(n). Recursive stack calls take at most n space in the worst case (single branch tree).