# 72ms c++ solution using one stack, O(n) time and space

• The idea is traversing the preorder list and using a stack to store all predecessors. curr_p is a predecessor of current node and current node is in the right subtree of curr_p.

For example, for the following bst with preorder 6,3,1,2,5,4,7:

``````              6
/  \
3    7
/  \
1   5
\   /
2  4
``````

We push to stack before we see 2. So at 2 the stack is 6,3,1. For 2, we pop stack until we see 3 which is greater than 2 and curr_p is 1. 2 is in left subtree of 3 and is right child of 1. Stack is 6,3,2 now. Then we see 5, and we pop stack until 6 and curr_p is 3. Stack now is 6,5. Then we see 4 and push to stack. At 7, we pop stack until empty and curr_p is 6.

``````bool verifyPreorder(vector<int>& preorder){
// using stack
int sz = preorder.size();
if(sz < 2) return true;
stack<int> s;
s.push(preorder[0]);
int curr_p = INT_MIN;
for(int i=1; i<sz; i++){
if(s.empty() || preorder[i]<s.top()){ // if current node is less than stack top, then go to left subtree
if(preorder[i]<curr_p) return false;
s.push(preorder[i]);
}
else{
while(!s.empty() && s.top()<preorder[i]){ //find curr_p such that current node is right child of curr_p
curr_p = s.top();
s.pop();
}
s.push(preorder[i]);
}
}
return true;
}``````

• Good explanation, great job!

• Compare to most voted one, this code is not fully optimized, but I think it is easier to understand!

• I think there is no need to make the first element special

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
if (preorder.size() < 2) return true;

stack<int> s;
int curNum = INT_MIN; // mark the number has been counted

for (int i = 0; i < preorder.size(); i++) {
if (s.empty() || s.top() > preorder[i]) {
if (curNum > preorder[i]) return false;
s.push(preorder[i]);
} else {
while (!s.empty() && s.top() < preorder[i]) {
curNum = s.top();
s.pop();
}
s.push(preorder[i]);
}
}
return true;
}
};

``````

• share my simpler code

``````class Solution {
public:
bool verifyPreorder(vector<int> &preorder) {
stack<int> s;
long prev = LONG_MIN;

for (const int &e : preorder) {
while (!s.empty() && e >= s.top()) {
prev = s.top();
s.pop();
}
if (e <= prev) {
return false;
}
s.push(e);
}
return true;
}
};

``````

• @yu23 Share my solution without using an explicit stack, we can use the input vector as the stack : )

``````bool verifyPreorder(vector<int>& preorder) {
stack<int> stk;
int lb = INT_MIN, stkTop = -1;
for(int i = 0; i < preorder.size(); i++) {
if(preorder[i] <= lb) return false;
while(stkTop >= 0 && preorder[stkTop] < preorder[i]) {
lb = preorder[stkTop];
stkTop--;
}
preorder[++stkTop] = preorder[i];
}
return true;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.