255. Verify Preorder Sequence in Binary Search Tree

• Difficulty: Medium

• Topics: Stack, Tree

• Similar Questions:

  • Binary Tree Preorder Traversal

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.

Consider the following binary search tree: 

     5
    / \
   2   6
  / \
 1   3

Example 1:

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

Example 2:

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

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

Solutions:

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        stack<int> stk;
        int lowerBound = INT_MIN;
        for (auto num : preorder) {
            if (num <= lowerBound)  return false;
            if (!stk.empty() && stk.top() == num)   return false;
            while (!stk.empty() && stk.top() < num) {
                lowerBound = stk.top();
                //cout << lowerBound << " " << num << endl;
                stk.pop();
            }
            stk.push(num);
        }
        return true;
    }
};