Verify Preorder Sequence in Binary Search Tree

Problem

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up

Could you do it using only constant space complexity?

Examples

Consider the following binary search tree:

Example1

Input: [5,2,6,1,3]
Output: false

Example2

Input: [5,2,1,3,6]
Output: true

Example3

Input: preorder = [1,3,2]
Output: true

Example4

Input: preorder = [1,2]
Output: true

Solution

Method 1 - Using Monotonic Decreasing Stack and Keeping Lower Bound

Key Observations

In a BST, for any node, all elements in its left subtree are smaller, and all elements in its right subtree are larger.
In preorder traversal, we first visit the root, then recursively visit the left and right subtrees.

Validation

While processing elements in the array, maintain the boundary (referred to as the low value) below which values cannot appear (since they belong to the left subtree).
Use a stack to simulate the traversal and validate the sequence:
- Push nodes onto the stack until nodes in the right subtree appear.
- Update the boundary (low) when backtracking occurs.

Algorithm

Walk through the preorder traversal, left subtree value < root's value < right subtree's value
We can see that, root value< upcoming right value in the array
If we know the root value, we can use it to determine whether if upcoming value is valid. So we use a lower to denote the lower_bound, which is also the root value, of the tree.
Use a stack to store the array from root to left subtree, whenever reach a node has greater value, pop value out of stack. Then store the last pop out value as lower bound.

Code

Java

class Solution {
    public boolean verifyPreorder(int[] arr) {
        int low = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        
        for (int num : arr) {
            if (num < low) {
                return false;
            }
            
            while (!stack.isEmpty() && num > stack.peek()) {
                low = stack.pop();
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

Python

class Solution:
    def verifyPreorder(self, arr: list[int]) -> bool:
        stack: list[int] = []
        low: int = float('-inf')
        
        for num in arr:
            if num < low:
                return False
            
            while stack and num > stack[-1]:
                low = stack.pop()
            
            stack.append(num)
        
        return True

Complexity

⏰ Time complexity: O(n), where n is the size of the input array, as each element in the array is processed once.
🧺 Space complexity: O(n) because the stack can contain up to n elements in the worst case. However, for well-balanced trees, the stack size is limited to the depth of the tree (O(log n)).

Dry Run

        50
     /       \
   17         76
  /   \       /
 9     23   54
  \    /     \
   14 19      72
  /          /
 12         67

preorder=[50,17,9,14,12,23,19,76,54,72,67]

Lets look at algo:

curr=50; stk=[50]
curr=17; stk=[50,17]
curr=9; stk=[50,17,9]

curr=14; We pop out 9; lower=9 and push 14; stk = [50,17,14]
curr=12; stk=[50,17,14,12]

curr=23; pop 12, 14, 17; lower=17 ; push 23 => stk=[50,23]
curr=19; push 19 => stk=[50,23,19]

curr=76; pop 19, 23, 50 and push 76; lower = 50, stk=[76]
curr=54; push 54; stk=[76, 54]
curr=72; pop 54, push 72; lower=54; stk=[76,72]
curr=67; push 67; stk=[76, 72, 67]

No element violated the lower bound, so the preorder is valid.