O(n) Solution easiest


#1

int Solution::solve(vector &a) {

stack<int> s;
int root = INT_MIN;

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

}


#2

Time Complexity is not O(N) but O(N Log(N)). You forgot to take the height of tree.


#3

hey nikhil i’m unable to make the preorder form the given A = [7, 7, 10, 10, 9, 5, 2, 8] there is a duplicate also can you please tell me how to make form this


#4

Well Actually BST don’t have repetitive values.
But in this question if you consider to place repetitive value to left of the parent which would be of same value as you can see repetitive values are together in the example therefore their won’t be any issue in handling BST and the tree will satisfy all the property of BST except unique values


#5

can you make the bst form this?


#6

The time complexity is indeed O(n). While the stack can be long and takes a long time to unwind in a certain iteration, the total number of stack pop operations cannot exceed that of the push operation (for the whole run, and also at any given time). As there are O(n) stack pushes, there are at most O(n) stack pops.

And the number of comparisons in the while loop is the number of stack pops + (n - 1), which is still O(n).