Skip to content

255. Verify Preorder Sequence in Binary Search Tree πŸ”’

Description

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= preorder.length <= 104
  • 1 <= preorder[i] <= 104
  • All the elements of preorder are unique.

 

Follow up: Could you do it using only constant space complexity?

Solutions

Solution 1

Thinking

Rebuilding the BST is heavier than needed. Preorder visits root, left, then right; a decreasing stack holds nodes that have not yet turned to their right subtree.

A value below the last popped lower bound is invalid. Otherwise pop every smaller top as the new bound and push the current value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stk = []
        last = -inf
        for x in preorder:
            if x < last:
                return False
            while stk and stk[-1] < x:
                last = stk.pop()
            stk.append(x)
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Deque<Integer> stk = new ArrayDeque<>();
        int last = Integer.MIN_VALUE;
        for (int x : preorder) {
            if (x < last) {
                return false;
            }
            while (!stk.isEmpty() && stk.peek() < x) {
                last = stk.poll();
            }
            stk.push(x);
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        stack<int> stk;
        int last = INT_MIN;
        for (int x : preorder) {
            if (x < last) return false;
            while (!stk.empty() && stk.top() < x) {
                last = stk.top();
                stk.pop();
            }
            stk.push(x);
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func verifyPreorder(preorder []int) bool {
    var stk []int
    last := math.MinInt32
    for _, x := range preorder {
        if x < last {
            return false
        }
        for len(stk) > 0 && stk[len(stk)-1] < x {
            last = stk[len(stk)-1]
            stk = stk[0 : len(stk)-1]
        }
        stk = append(stk, x)
    }
    return true
}

Comments