255

255. Verify Preorder Sequence in Binary Search Tree (Medium)

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?

Companies:
VMware

Related Topics:
Stack, Tree, Binary Search Tree, Recursion, Monotonic Stack, Binary Tree

Similar Questions:

• Binary Tree Preorder Traversal (Easy)

Solution 1. Monotonic Stack

// OJ: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    bool verifyPreorder(vector<int>& A) {
        stack<int> s;
        int mn = INT_MIN;
        for (int n : A) {
            if (n < mn) return false;
            while (s.size() && s.top() < n) {
                mn = s.top();
                s.pop();
            }
            s.push(n);
        }
        return true;
    }
};

Or if we are allowed to change the input array to simulate the stack

// OJ: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1) if we don't count the space used by the input array.
class Solution {
public:
    bool verifyPreorder(vector<int>& A) {
        int mn = INT_MIN, j = -1;
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] < mn) return false;
            while (j >= 0 && A[j] < A[i]) mn = A[j--];
            A[++j] = A[i];
        }
        return true;
    }
};