# C++ Explanation Using Stack

• We use a `Monotonic Stack`

when we scan the sequence, we have 2 options:

1. `put it to the left`, if `current number` is less than `the above number`
may violate lower bound
insert 1 and 3 is different
``````2
\
5
/
(1)
(3)
``````
1. `put it to the right`, if `current number` is larger than `the above number`
insert 2 and 4 is different
we increase `largest_seen` as little as possible to accommodate nodes as many as possible
``````   3
/ \
1  (4)
\
(2)
``````
1. `no above number`, i.e. stack is empty
It is definitely safe to push current number to the stack

Notice: `the above number` is at the top of the stack.

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

for (const int &num : preorder) {
if (!s.empty() && num < s.top()) { // put it to the left
if (num <= largest_seen) {
return false;
}
} else {  // put it to the right
while (!s.empty() && num >= s.top()) {
largest_seen = s.top();  // num is at right of it
s.pop();
}
}
s.push(num);
}
return true;
}
};
``````

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