L46. Check if a tree is a BST or BT | Validate a BST

[@takeUforward]

Please do like the video, and let me know in the comments, did you understand?

[@kvv6452]

C++ in github code needs a minor correction. It should be LONG_MIN or LONG_MAX.

[@notinrange]

Why does this Approach not work for all test cases in c++?

[@abinashgupta670]

In space complexity we should consider the auxiliary space for recursion i.e. O(H) .

[@tusharjain5882]

@@notinrange This solution will not work when there is only one node whose value is INT_MIN or INT_MAX

[@aswinipanguluri5440]

It will not work for duplicate numbers

[@harshmittal3128]

Another approach to this question could be to use inorder traversal and make sure it is strictly increasing . For the inorder traversal we could use morris traversal so that no auxillary stack space is used which in case of recursion would have been O(n) .
The code is below:
bool isValidBST(TreeNode* root) {
bool b=true;
bool first=true;
int prev;
TreeNode* curr=root;
while(curr){
if(curr->left==NULL){
if(first){
prev=curr->val;
first=false;
}
else{
if(curr->valval;
}
}
curr=curr->right;
}else{
TreeNode* tmp=curr->left;
while(tmp->right && tmp->right!=curr){
tmp=tmp->right;
}
if(tmp->right==NULL){
tmp->right=curr;
curr=curr->left;
}
else{
if(curr->valval;
}
tmp->right=NULL;
curr=curr->right;
}
}
}
if(b)
return true;
return false;
}

[@mewaconite]

i thought the exact same thing !

[@anujrathore5726]

i did thought this , and did this by myself .

[@imPriyansh77]

Yes, I thought the same

[@dhruvdangi8923]

great use of this property man👍👍

[@akashpurbia4390]

My Solution:
Intuition:
We can simply use inorder traversal because if the given BT is BST then the inorder traversal will be in sorter order, and we check this whenever we visit a node. If we find that the any single node’s value is not increased from the last value then we can say that the tree is not BST.
class Solution
{
public:
//Function to check whether a Binary Tree is BST or not.
int temp = INT_MIN;
void Inorder(Node *root, bool &flag)
{
if(!root) return;
Inorder(root->left, flag);
if(tempdata)
temp = root->data;
else
flag = false;
Inorder(root->right, flag);
}
bool isBST(Node* root)
{
// Your code here
bool flag = true;
Inorder(root, flag);
return flag;
}
};

[@yashshrivastav7286]

very nice approach

[@jaishriharivishnu]

never use global variable

[@callmeMr.X]

abe wrong ans h..................when input is [-2147483648]

[@tulika2863]

Happy to see that you are back with videos on TUF. TUF is ❤️. This tree series has helped me a lot in one of my recent interview.

[@Mohit_Q]

where are you working now ???

[@noobcoder5383]

we can also do a inorder traversal , taking a current varaible , where we can check if my curren value is greater than the stored value

[@optimus_prime01]

ysssssssssssssssssssssssssssssssssssssssssssssssss

[@DhruvParmar-gm4ke]

so true

[@bharat_alok11]

class Solution {
public:
bool inorder(TreeNode* root,long long &data){
if(root==nullptr) return true;
//go to left
bool l = inorder(root->left,data);
//processing root
if(root->val > data){
data = root->val;
}else{
return false;
}
//go to right
bool r = inorder(root->right,data);
return l && r;
}
bool isValidBST(TreeNode* root) {
long long data = LLONG_MIN;
return inorder(root,data);
}
};

[@aasheesh6001]

We can also use Inorder because Inorder of BST is sorted. so we can just do inorder transversal and use a previous pointer which track previous number. Here is my code:
public boolean isValidBST(TreeNode root) {
inorder(root);
return flag;
}
boolean flag = true;
long prev = Long.MIN_VALUE;
private void inorder(TreeNode root) {
if(root == null) return;
inorder(root.left);
if(prev >= root.val){
flag = false;
return;
}
else prev = root.val;
inorder(root.right );
}

[@U2011-n7w]

why return and break are not working in morris traversal in leetcode in this and previous question

[@gorilla_coder-el6kf]

@@U2011-n7w the tree should be unthreaded before returning

[@ajayagrawal2067]

Good solution

[@ajaykarthik9314]

My approach was , perform inorder and check wheather it is in increasing order or not

[@piyushacharya7696]

WooooW! man what an idea.🤩🤩

[@aryanchaurasia1081]

I thought the same

[@AbdulKareem-np6wp]

I think we are same 😂

[@amartarei4357]

I also used the same approach

[@letitbex221]

did same

[@shivakumarranade1483]

Greatt explanation!!. But actually we can also perform an inorder traversal as it will give sorted order and store it in a vector or something. Then iterate through the vector and if (i+1)th node is lesser than (i)th node then return false or true.

[@sumurthdixit8482]

This can be done without a vector by creating a reference variable lastValue=LLONG_MIN, at each recursive call in inorder, lastValue < currentNode->val must maintain.

[@AdityaDahiya99]

Increases the space complexity

[@tanaykamath1415]

One can also solve this using inorder traversal, without needing to store it in an array!
like this:
class Solution {
long prev;

public boolean isValidBST(TreeNode root) {
prev=Long.MIN_VALUE;
if(root.val==Long.MIN_VALUE || root.val==Long.MAX_VALUE){
return false;
}

return inorderCheck(root);
}

boolean inorderCheck(TreeNode node){
if(node==null){
return true;
}

boolean flag=inorderCheck(node.left);

if(!flag){
return false;
}


if(prev>=node.val){
return false;
}else{
prev=node.val;
}


flag=inorderCheck(node.right);

return flag;
}

}

[@subhajitdey135]

My first intuition was to check whether for every node the left_max(max of nodes on the left) and right_min(min of nodes on the right) , left_maxdata

[@shreyasvishwakarma8979]

I think one added Solution is : Take the inorder of given BST ( why ? INOREDER OF BST is ALWAYS SORTED) . Check if it is sorted or not . If sorted return "YES" else "NO"
Time Complexity : O(n)
Space Complexity : O(n) --> We are using extra space to store node values

[@neerajmahapatra5239]

Don't store nodes just compare the data and it will not require extra space

[@uniquematrixhc7619]

i watched your video for 1:48 & got my solution thanks

[@sanjubaloria2745]

Sir you nailed the tree series.Never find such kind of tree series before

[@LokeshSharma-hm5jz]

i was confident about my code, and then this test case appears.. Thanks

[@av21015]

you made it really simpler, it was indeed a tough one. your choice of test case also explains the concept really well.

[@shwetanknaveen]

Code using int max,min parameters-->
class Solution {
public:
bool recHelper(TreeNode* root,int max,int min)
{
if(!root)//empty node doesn't violate BST property
return true;

if(root->val>max || root->valval==INT_MIN)//if node value is INT_MIN
{
if(root->left) return false;//We can't go left as we can't afford value less than INT_MIN
else return recHelper(root->right,max,root->val+1);//if there is no left child then we can go usual way to right
//subtree
//We can't leave this else case for default case otherwise there, while checking for left subtree, it will try
//to store INT_MIN-1 in int which will cause overflow
}

if(root->val==INT_MAX)//if node value is INT_MAX
{
if(root->right) return false;//We can't go right as we can't afford value greater than INT_MAX
else return recHelper(root->left,root->val-1,min);//if there is no right child then we can go usual way to left
//subtree

//We can't leave this else case for default case otherwise there, while checking for right subtree, it will try
//to store INT_MAX+1 in int which will cause overflow
}

return recHelper(root->left,root->val-1,min) && recHelper(root->right,max,root->val+1);
//The default case to check both subtrees for BST property
}
bool isValidBST(TreeNode* root) {
return recHelper(root,INT_MAX,INT_MIN);//initially max value can be INT_MAX and min value can be INT_MIN
}
};

[@ritikshandilya7075]

bhai ek hi dil he , kitni baar jitoge . Amazing explanation 💯

[@soumyodeepdey5237]

Another approach can be verifying whetehr the inorder traversal of the tree yields a sorted arrray or not. But it would require two traverSALS. ONE TO CONSTRUCT THE INORDER TRAV AND THEN TO traverse the array to check for sorted or not. So TC is O(2n). Also need an extra space of O(n) for the inorder array. Suboptimal.

[@akshat_1404]

Thanks man for this amazing explanation.
It is a great method to use concept of upper and lower bound.

[@rakshitpandey7517]

Store the inorder traversal of the Binary Search Tree and for valid BST it should be in sorted form and check if two adjacent elements the before element is greater than or equal to after element, then return false(BST Should have unique data , so, if two adjacent are same, we are returning false), else return true.
Time Complexity-O(n)
Space Complexity - O(n)

[@tanaykamath1415]

you don't need to store it, just cache the previous value of the inorder traversal in a global variable and compare it to the current value!

[@thallapakuteja2350]

@Rakshit Pandey for checking whether it is sorted or not u need to sort the elements which takes O(nlogn) tc

[@rakshitpandey7517]

@@thallapakuteja2350 No dude. Store the inorder as it gives sorted answer for BST and TC of inorder traversal is in Linear time.

[@jitinroy2246]

@@thallapakuteja2350
code in java
tc- N, sc- N
/*
BST ka inorder is always in ascending order
make a arraylist and do inorder of the tree
traverse all the stored values and if i-1 > i then it's not in ascending order and return false, else return true
*/
public class Solution
{
//Function to check whether a Binary Tree is BST or not.
boolean isBST(Node root)
{
// code here.
ArrayList al=new ArrayList();
helper(root,al);
for(int i=1; i al.get(i)){
return false;
}
}
return true;
}
void helper(Node root, ArrayList al){
if(root==null){
return;
}
helper(root.left,al);
al.add(root.data);
helper(root.right,al);
}
}

[@zanies6288]

inorder of a bst is always sorted so you can use that logic as well to solve this. class Solution {
private:
void dfs(TreeNode* root, vector&v){
if(!root) return;
dfs(root->left, v);
v.push_back(root->val);
dfs(root->right,v);
}
public:
bool isValidBST(TreeNode* root) {
vectorv;
dfs(root, v);
for(int i=1;i v[i-1]) continue;
else{
return false;
}
}
return true;

}
};

[@krishnaradhey2814]

Another approach can be to traverse via morris traversal without using any memory
and maintaining pre_count and current_count to check if current value is greater than previous one,
We have to maintain INT_MIN case here
CODE:-
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root->left== nullptr && root->right==nullptr)return true;
int pre = INT_MIN;
int aim = 0;
bool cond = true;
while(root)
{
if(!root->left)
{
if(pre == INT_MIN && root->val == INT_MIN && aim == 0)
{
aim++;
}
else if(root->val val;
root = root->right;
}
else if(root->left)
{
TreeNode * prev = root->left;
while(prev->right != nullptr && prev->right != root)
{
prev = prev->right;
}
if(!prev->right )
{
prev->right = root;
root=root->left;
}
else if(prev->right ==root)
{
prev->right = nullptr;
if(root->val val;
root = root->right;
}
}
}
return cond;
}
};
DO LIKE THIS COMMENT

[@PradipKumar-zi2pz]

My solution (New Approach):
We know that every node value in the left subtree must be less than the root node's value, and every node value in the right subtree must be greater than the root node's value.
Intuition:
Consider this: if the root node's value is greater than the maximum value of the left subtree, then the root will naturally be greater than all the nodes in the left subtree. Similarly, for the right subtree, if the root node's value is less than the minimum value of the right subtree, then the tree satisfies the BST property. Otherwise, it does not.
Therefore, we can return the maximum value of the left subtree and the minimum value of the right subtree and compare all three values to determine if the tree is a BST.
If maxValueOfLeftSubtree < root value < minValueOfRightSubtree ---> Yes
Else ----> No
def func(self, root):
if root is None:
return float('inf'), float('-inf')
lmin, lmax = self.func(root.left)
rmin, rmax = self.func(root.right)
if lmin is False or rmin is False:
return False, False
if not (lmax < root.val < rmin):
return False, False
return min(root.val, lmin, rmin), max(root.val, lmax, rmax)
def isValidBST(self, root: Optional[TreeNode]) -> bool:
left, right = self.func(root)
return True if left is not False and right is not False else False

[@ec039venom4]

At node 12 ,range should be [10,INT_MAX] ??time -4:00

[@ankitduttavlogs9206]

what about inorder traversal and checking current value with previous value ?? TC - O(n) for worst, SC - O(1)

[@ravishranjan7135]

We can also solve this question using morris Traversal (in order). Inorder has a special property, it arranges all nodes in ascending order so we take (data) variable and initialize with min value and compare with (curr.val). If it disobeys the property of Inorder then directly return False, otherwise update the data every time, and at last return True
TC--O(N)
SC--O(1)
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
data = float('-inf')
curr = root

while curr is not None:

if curr.left is None:
if data>=curr.val:
return False
data = curr.val
curr = curr.right

else:
pre = curr.left

while pre.right is not None and pre.right is not curr:
pre = pre.right

if pre.right is None:
pre.right = curr
curr = curr.left

else:
pre.right = None
if data>=curr.val:
return False
data = curr.val
curr = curr.right
return True

[@takeUforward]

Works!

[@ScienceSeekho]

Thank me later! C++ implementation
class Solution {
public:
bool isValidBST(TreeNode* root) {
return help(root, LONG_MIN, LONG_MAX);
}

bool help(TreeNode* root, long min, long max){
if(!root) return true;
if(root->val val >= max) return false;
return help(root->left, min, root->val) && help(root->right, root->val, max);
}
};

[@DevanshuAugusty]

THANX IT HELPED

[@MadhavGupta-fi2tu]

@@DevanshuAugusty ++

[@HARSHSHARMA-ic6qo]

Thanking you later.

[@_AmbujJaiswal]

@@MadhavGupta-fi2tu thanks madhav lord

[@spiral546]

thx

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@thanujreddy6097]

Thank you so much this is the easy explanation i have found

[@AnujKumar-bw2bg]

another approach using in order without using any extra space
class Solution {
public:
int ans;
bool b=true;
int count=0;
bool isValidBST(TreeNode* root) {
if (root->left) isValidBST(root->left);
count++;
if (count==1){
ans=root->val;
}
else {
if (root->val > ans){
ans=root->val;
}
else b=false;
}
if (root->right) isValidBST(root->right);
return b;
}
};

[@rahulguptad.t.u5802]

in case anyone facing the error with the int min and int max test case : then here you can intalize it with long long :
class Solution {
public:
bool isBST(TreeNode* root , long long min , long long max){
if(root==NULL)return true;
if(root->valval>=max)return false;
bool left =isBST(root->left, min, root->val);
bool right=isBST(root->right, root->val, max);
return left&&right;
}
bool isValidBST(TreeNode* root) {

return isBST( root, LLONG_MIN, LLONG_MAX);

}
};

[@apmotivationakashparmar722]

Thank you so much Striver !

[@jarangvinayak.5435]

class Solution {
long value=Long.MIN_VALUE;
boolean valid=true;
public boolean isValidBST(TreeNode root) {
inorder(root);
return valid;
}
public void inorder(TreeNode root){
if(root==null){
return ;
}
inorder(root.left);
if(value>=root.val) valid=false;
value=root.val;
inorder(root.right);
}
}

[@neilbohr6015]

yes bro same approach also we can use morris traversal

[@sarthakyadav9950]

Thanks Man!!!. I was having a hard time understanding this.

[@026harshagarwal9]

Sir, can we also find the in order traversal of given BT and if elements are sorted then it is BST otherwise it is not a BST

[@adityajain5101]

YES I did that it was accepted in leetcode TC=O(n) and SC=O(N) + O(N) (stack space recrsive)

[@eziosan7208]

Instead of complete inorder traversal array, we just need to keep a variable, to store the inorder, if the new inorder is less than the previeous one, its not a bst

[@026harshagarwal9]

@@eziosan7208 yes that is also fine 👍

[@adityan5302]

If Python Users finding any sort of difficulty refer this
Try for yourself, if you fail then only refer this
class Solution:

def find(self, root, left, right):

if root is None:
return True

if root.data>=right or root.data

[@amanshah1650]

Code using morris traversal :-
bool isValidBST(TreeNode* root) {
int ans;
bool res=true, flag=false;
coutleft;
while(prev->right&&prev->right!=root)prev=prev->right;
if(prev->right==NULL){
prev->right=root;
root=root->left;
}
else{
if(flag&&root->valval;
flag=true;
prev->right=NULL;root=root->right;
}
}
else{
if(flag&&root->valval;
flag=true;
root=root->right;
}
}
return res;
}

[@abhaykumarsingh3884]

Approach using Inorder
class Solution {
TreeNode prev=null;
public boolean isValidBST(TreeNode root) { //TC:O(N) and Auxiliary space:O(N)
if(root==null){
return true;
}
boolean t1= isValidBST(root.left);
if(!t1){
return false;
}
if(prev != null){
if(prev.val

[@saksham9170]

Bhaiya, I've completed the sde sheet, should I do more leetcode now or should I do core subjects+other questions like LLD. My goal is to clear interviews of good prod based company.

[@newtanagmukhopadhyay4716]

dont stop practicing from leetcode. practice some more similar problems if possible. like you can maybe start doing the love babbar 450 problem sheet right now. also sidewise, doing development+focusing on core CS topics is very important. do that as well. GATE Smashers would be a very good choice.

[@YVGamers]

if u are having trouble to solve this problem on leetcode then use LONG_MIN and LONG_MAX rather than INT_MIN and INT_MAX

[@rameshpokhriyalnishank7445]

Sir , i have a doubt. Can we do it in constant space by morris inorder and checking for each element to be >= previous one .

[@PankajGoyal-z8s]

edge case not covered?
where val is actually INT_MAX or INT_MIN

[@budhadityachatterjee6270]

Shubho Bijaya !!
Diwali te ki DP Series ashbe ?

[@tech_wizard9315]

Is your trees series enough to crack tech giant's interviews like Microsoft linkedin level companies

[@takeUforward]

Yes for trees topic, more than enough!

[@chandantyagix]

Here, Stack Would be taking O(n) space in worst case when we do dfs, How about instead of that ... we just do the inorder traversal, keep it in an array and check whether that is sorted or not?

[@AnujYadav-pb5td]

Why to keep it in an array..you can check that while Traversing the tree

[@chandantyagix]

@@AnujYadav-pb5td Yeah, So We can just do that Right?

[@dhanarajs2707]

Instead of checking whether it is sorted , you have to verify that it is strictly increasing inorder traversal array that you get at the end.

[@dorababuarig765]

NO RECURSION AND O(N) TIME:
We can solve this using a simple iterative inorder traversal. As if the tree is bst for every subnode then the numbers in inorder traversal should be in ascending order.
bool isValidBST(TreeNode* root) {
bool first=true;
int m;
if(!root){
return false;
}
stack s;
s.push(root);
root=root->left;
while(!s.empty() || root){
if(root){
s.push(root);
root=root->left;
}
else{
TreeNode* temp=s.top();
s.pop();
if(first){
first=false;
m=temp->val;
}
else{
if(m>=temp->val){
return false;
}
else{
m=temp->val;
}
}
root=temp->right;
}
}
return true;
}

[@anshulgoel1940]

Can we do morris traversal and only have lower bound, this will have better complexity

[@vivektiwari143]

Everyone, this code also works fine, this can be improved?
bool checkBST(Node *node)
{
if(node->left==NULL && node->right==NULL)
{
return true;
}
Node *left_node=node->left;
Node *right_node=node->right;
if(node->data>left_node->data && node->datadata)
{
return checkBST(node->left) && checkBST(node->right);
}
return false;
}
Please give review on the above code

[@tusharjain5882]

Simple Solution: without storing the inorder traversal in vector or array.
Time Complexity: O(N)
Space Complexity: O(1) by ignoring Auxiliary stack space
void isValidBST(TreeNode *root,long long int & data,bool & isValid){
if(root==NULL){
return;
}

isValidBST(root->left,data,isValid);
if(root->val > data){
data=root->val;
}else{
isValid=false;
return;
}
isValidBST(root->right,data,isValid);
}

bool isValidBST(TreeNode* root) {
bool isValid=true;
long long int data=LONG_MIN;
isValidBST(root,data,isValid);
return isValid;
}

[@pranavsharma7479]

my approach was O(n) time and O(n) space, but striver one is best as its O(1), i used inorder sorted property and made a vector , and checked in that vector all are sorted or not

[@reppee4392]

it's not O(1) he's ignoring the recursion stack space O(log(n))

[@abcsumits]

what if i check for every node left max should be less than current node and rightnode should be less than right min.

[@nagavedareddy5891]

Huge respect...❤👏

[@53_manishkumar_it54]

helpful lecture and comments also

[@mohdhammadsiddiqui7598]

What if we use inorder sorted property of bst if at any point sorting is not maintaned we we will return false

[@taqimustafa7665]

class Solution {
int flag=1;TreeNode prev=null; //int prev=Integer.MIN_VALUE;
public void inOrder(TreeNode root)
{
if(root==null)
return;

inOrder(root.left);
if(prev!=null && root.val=root.val)
{
flag=0;
return;
}
prev=root;
//prev=root.val;
inOrder(root.right);
}
public boolean isValidBST(TreeNode root) {
if(root==null)
return true;
inOrder(root);
return (flag==1);
}
}

[@baibhavmandal9398]

If root nodes value was equal to INT_MIN then would this code work. Assume that root don't have left node.

[@ishangujarathi10]

crystal clear intuition < 3!!!!

[@aayushgakhar3525]

intuitive approach++

[@anishaa3298]

this is amazing, thank you!

[@devendrapatil3205]

you said SC = O(1), whats about recursion

[@ayoubelhioui2205]

thank you so much for the explanation

[@harshidatanku6561]

Sir how is the space complexity one we have recurssion of entire left subtree and right subtree so the stack space used is o(n)

[@rahulshetty3849]

No extra space is used, space of given tree which to be traversed is not considered, if you use any extra space then the space will be taken into account

[@manishchitre5130]

@@rahulshetty3849 : But don't you think the recursive call stack will have recursive function stored and in this case the space complexity is O(n)?

[@vigneshgopinath6795]

To be a BST should the BT should be balanced?

[@AdityaKumar-be7hx]

Here's another way using inorder traversal
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode* prev=nullptr;
return isValidBST(root, prev);
}
bool isValidBST(TreeNode* root, TreeNode*& prev){
if(root==nullptr) return true;
// return false if the left subtree is not BST
if(!isValidBST(root->left, prev)) return false;
if(prev!=nullptr and prev->val >= root->val) return false;
prev=root;
return isValidBST(root->right, prev);
}
};

[@bharath3387]

Excellent brother, I was looking for this to avoid edge cases in lc

[@aryamangupta3919]

This code fails on duplicate value,
what if 1 has left child as 1

[@NaveensinglaYT]

*This code will pass all the edge cases*
bool check(node *root, int max, int min)
{
if(!root) return true;
if(root->val>max || root->valleft,root->val-1,min) && check(root->right,max,root->val+1);
}
bool isValidBst(node *root)
{
return check(root, INT_MAX, INT_MIN);
}

[@TON-108]

LeetCode 98:
C++
class Solution {
public:
bool bst(TreeNode* root, long long mini, long long maxi)
{
if(root == nullptr)
return true;
if(root->val >= maxi || root -> val left, mini, root->val) && bst(root->right, root->val, maxi));
}
bool isValidBST(TreeNode* root) {
return bst(root, (long long)LONG_MIN, (long long)LONG_MAX);
}
};

[@parthsalat]

Here are my detailed notes for this question:
garmadon.notion.site/Validate-Binary-Search-Tree-81d9e081d588424691a163570fc48194

[@abhishekkapoor7955]

3 lines of code! thanks bro

[@b_01_aditidonode43]

what an amazing explaination:)

[@sumitrajpal29]

Striver is best!!!

[@shiwalikttsrivastava1497]

sir can we do by checking inorder traversal of bst is sorted or not

[@oqant0424]

#include
class Solution {
public:
bool helper(TreeNode* root,long low,long high){
if(!root)return true;
if(root->valval>=high)return false;
return helper(root->left,low,root->val) && helper(root->right,root->val,high);
}
bool isValidBST(TreeNode* root) {
return helper(root,LONG_MIN,LONG_MAX);
}
};

[@peregrine17]

use this logic if you understand it better
if(root == NULL){
return true;
}
if(!(root -> val > min && root -> val < max)){
return false;
}
return help(root-> left, min, root -> val) && help(root->right, root->val, max);

[@utkarshsaxena7445]

This Code will Both run on GFG & LeetCode
class Solution
{
public:
//Function to check whether a Binary Tree is BST or not.
bool isBST(Node* root)
{
Node* prev = NULL;
return validate(root, prev);
}
bool validate(Node* node, Node* &prev)
{
if (!node) return true;
if (! validate(node->left, prev)) return false;
if (prev != NULL && prev->data >= node->data) return false;
prev = node;
return validate(node->right, prev);
}
};

[@aryanchaurasia1081]

Which compiler is he using

[@dipanshusingh]

Love your work bro.♥

[@arfatbagwan48]

You looks like munnawar Faruqui

[@sunilswami6796]

bro code link is of checkBST can u put right code link

[@tejasghone5118]

if we are passing arguments as value in recursive function then will it also count in space complexity?Because for each call it will generate 2 new variables which is equivalent to generating array of sz 2*n if tree is linear

[@bhavikasodagum1121]

when i submit it says wrong ans :|

[@zealkapadiya4783]

Clone a graph vala video please jaldi upload karna..Our placement process has started in college 😅😅😅

[@takeUforward]

Okay.. trees k bd !!

[@shruthidasa7139]

The C++ implementation of Morris Inorder iterative traversal is giving runtime error in leetcode. Can anyone say what went wrong here?
class Solution {
public:
bool isValidBST(TreeNode* root)
{
int dat=INT_MIN;
TreeNode* curr=root;
while(curr)
{
if(curr->left==NULL)
{
if(dat>=curr->val) return false;
dat=curr->val;
curr=curr->right;
}
else
{
TreeNode* prev=curr->left;
while(prev->right!=NULL and prev->right!=curr)
{
prev=prev->right;
}
if(prev->right==NULL)
{
prev->right=curr;
curr=curr->left;
}
else{
prev->right=NULL;
if(dat>=curr->val) return false;
dat=curr->val;
curr=curr->right;
}
}
}
return true;

}
};

[@sonicboom6635]

I guess it's mostly because of the return in if conditions as this will leave unwanted threads within the given input tree and lead to runtime issue as I faced it too

[@Account-je9ml]

24/01/2022...thanks anna....

[@mayankrohilla4105]

-INT_MIN == INT_MAX ??

[@sahllsaharn4664]

bhaiya i done it another wa and in o(n) i get the inorder using morris traversal and checked it is it sorder or not is thsi approach correct to present in a interview !!!
and it passed all test cases on leetcode;
thanks

[@prashantpandey2848]

range will be problem here

[@Learnprogramming-q7f]

Thank you Bhaiya

[@UECAshutoshKumar]

Thank you sir

[@_PAYALGAIKWAD]

huge respect❤

[@shouvikdatta6831]

Bhi, diwali pe DP series ayega kya?

[@amannama198]

DP series won't come #false_hopes

[@alesblaze4745]

thanks mate!

[@codding32world50]

CPP CODE
class Solution
{
public:
bool isValidBST(TreeNode *root)
{
return isValidBST(root, LONG_MAX, LONG_MIN);
}
bool isValidBST(TreeNode *root, long minVal, long maxVal)
{
if (root==NULL)
return true;
if (root->val >= maxVal || root->val left, minVal, root->val) && isValidBST(root->right, root->val, maxVal);
}
};

[@SuperWhatusername]

understand thanks

[@s.g.prajapati3597]

Awesomeeeee!!!!!

[@adityapandey23]

Understood

[@akhilesh59]

Understood :)

[@shashamnk2525]

If the root value is Integer.MAX_VALUE then this solution might not work.

[@anshumaan1024]

that why use LONG_MAX, LONG_MIN

[@hitheshpk6030]

UNDERSTOOD

[@jaiminsolanki5478]

Understood