Problem description:

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:

1
2
3
4
5
    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?

Solution:

  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.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Push 50
Push 17 
Push 9
(read 14, 14 > 9)
Pop 9 (lower bound = 9)
Push 14
Push 12
(read 23, 23 > 12)
Pop 12
Pop 14
Pop 17 (lower bound = 17)
Push 23
(read 76, 76 > 23)
Pop 23
Pop 50 (lowerbound = 50)
Push 76
Push 54
(read 72, 72 > 54)
Pop 54 (lower bound = 54)
Push 72
Push 67

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

reference: