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:

1
2
3
4
5

     5
    / \
   2   6
  / \
 1   3

Example1

1
2

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

Example2

1
2

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

Example3

1
2

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

Example4

1
2

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

  1. Walk through the preorder traversal, left subtree value < root's value < right subtree's value
  2. We can see that, root value< upcoming right value in the array
  3. 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.
  4. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

        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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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.