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

Entire DSA Course: takeuforward.o...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/take...
#treeSeries #striver #placements

[@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 .

[@priyanshkumar17]

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

[@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); } };

[@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

[@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 ???

[@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

[@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; } }

[@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

[@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

[@LokeshSharma-hm5jz]

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

[@sanjubaloria2745]

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

[@ankitduttavlogs9206]

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

[@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

[@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); } }

[@av21015]

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

[@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!

[@shwetanksingh5208]

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 } };

[@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 👍

[@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; } };

[@akshat_1404]

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

[@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

[@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.

[@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; }

[@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); } };

[@thanujreddy6097]

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

[@stith_pragya]

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

[@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 .

[@ritikshandilya7075]

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

[@uniquematrixhc7619]

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

[@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.

[@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; } };

[@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

[@Account-je9ml]

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

[@ec039venom4]

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

[@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))

[@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!

[@sarthakyadav9950]

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

[@budhadityachatterjee6270]

Shubho Bijaya !! Diwali te ki DP Series ashbe ?

[@anishaa3298]

this is amazing, thank you!

[@53_manishkumar_it54]

helpful lecture and comments also

[@aayushgakhar3525]

intuitive approach++

[@abcsumits]

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

[@ishangujarathi10]

crystal clear intuition < 3!!!!

[@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)?

[@baibhavmandal9398]

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

[@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

[@anshulgoel1940]

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

[@nagavedareddy5891]

Huge respect...❤👏

[@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

[@ayoubelhioui2205]

thank you so much for the explanation

[@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); } }

[@vigneshgopinath6795]

To be a BST should the BT should be balanced?

[@devendrapatil3205]

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

[@parthsalat]

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

[@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; }

[@mohdhammadsiddiqui7598]

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

[@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

[@b_01_aditidonode43]

what an amazing explaination:)

[@UECAshutoshKumar]

Thank you sir

[@Shivi32590]

thankyou

[@shiwalikttsrivastava1497]

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

[@aryamangupta3919]

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

[@abhishekkapoor7955]

3 lines of code! thanks bro

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@s.g.prajapati3597]

Awesomeeeee!!!!!

[@SuperWhatusername]

understand thanks

[@aryanchaurasia1081]

Which compiler is he using

[@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

[@alesblaze4745]

thanks mate!

[@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; }

[@zealkapadiya4783]

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

[@takeUforward]

Okay.. trees k bd !!

[@sumitrajpal29]

Striver is best!!!

[@shaiksoofi3741]

understood

[@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); }

[@arfatbagwan48]

You looks like munnawar Faruqui

[@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); } };

[@tanmayjain5576]

Understood

[@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);

[@dipanshusingh]

Love your work bro.♥

[@agx111]

nice

[@tanishkumar6682]

understood

[@mayankrohilla4105]

-INT_MIN == INT_MAX ??

[@iamnoob7593]

US

[@hitheshpk6030]

UNDERSTOOD

[@abhinavsingh9720]

Thanks

[@prashantpandey2848]

range will be problem here

[@sunilswami6796]

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

[@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); } };

[@avanishmaurya2034]

Nice

[@dreamyme543]

Understood:)

[@girikgarg8]

Done!

[@CSEA_58ShayoriBhowmick]

❤❤❤

[@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

[@_PAYALGAIKWAD]

huge respect❤

[@bhavikasodagum1121]

when i submit it says wrong ans :|

[@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); } };

[@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

[@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

[@shouvikdatta6831]

Bhi, diwali pe DP series ayega kya?

[@amannama198]

DP series won't come #false_hopes