Simple C++ solution O(n) using stack


#1
int Solution::solve(vector<int> &pre) {
stack<int> s;
int root = INT_MIN;

for(int i =0;i<pre.size();i++){
    if(root > pre[i]){
        return 0;
    }
    while(!s.empty() && s.top()<pre[i]){
       root = s.top();
       s.pop();
    }
    s.push(pre[i]);
}
return 1;

}


#2

Can you explain the logic behind it


#3

Hi Jayesh can you please explain the logic behind this code.


#4

In pre-order traversal we can visualize that if we encounter greater number than
root node (or current node) then all number after that encountered greater number
should be greater than root node(or current node),if it happens then return (1)
otherwise return (0)


#5

i think if we find the next largest element we start i to n-1 up to 0 . if this is wrong please tell me why?


#6

This solution gives output 1 for {7, 10, 7}. Isn’t it wrong as this is not a valid preorder traversal of BST?