Це відео не доступне.
Перепрошуємо.
L46. Check if a tree is a BST or BT | Validate a BST
Вставка
- Опубліковано 19 сер 2024
- Entire DSA Course: takeuforward.o...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/take...
#treeSeries #striver #placements
Please do like the video, and let me know in the comments, did you understand?
C++ in github code needs a minor correction. It should be LONG_MIN or LONG_MAX.
Why does this Approach not work for all test cases in c++?
In space complexity we should consider the auxiliary space for recursion i.e. O(H) .
@@notinrange This solution will not work when there is only one node whose value is INT_MIN or INT_MAX
It will not work for duplicate numbers
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;
}
i thought the exact same thing !
i did thought this , and did this by myself .
Yes, I thought the same
great use of this property man👍👍
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;
}
};
very nice approach
never use global variable
My approach was , perform inorder and check wheather it is in increasing order or not
WooooW! man what an idea.🤩🤩
I thought the same
I think we are same 😂
I also used the same approach
did same
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
ysssssssssssssssssssssssssssssssssssssssssssssssss
so true
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);
}
};
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.
where are you working now ???
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 );
}
why return and break are not working in morris traversal in leetcode in this and previous question
@@U2011-n7w the tree should be unthreaded before returning
Good solution
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.
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.
Increases the space complexity
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;
}
}
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
Don't store nodes just compare the data and it will not require extra space
Sir you nailed the tree series.Never find such kind of tree series before
i was confident about my code, and then this test case appears.. Thanks
you made it really simpler, it was indeed a tough one. your choice of test case also explains the concept really well.
Thanks man for this amazing explanation.
It is a great method to use concept of upper and lower bound.
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)
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!
@Rakshit Pandey for checking whether it is sorted or not u need to sort the elements which takes O(nlogn) tc
@@thallapakuteja2350 No dude. Store the inorder as it gives sorted answer for BST and TC of inorder traversal is in Linear time.
@@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);
}
}
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
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
}
};
bhai ek hi dil he , kitni baar jitoge . Amazing explanation 💯
i watched your video for 1:48 & got my solution thanks
Thank you so much this is the easy explanation i have found
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;
}
};
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);
}
};
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
Works!
what about inorder traversal and checking current value with previous value ?? TC - O(n) for worst, SC - O(1)
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;
}
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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;
}
};
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);
}
}
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
YES I did that it was accepted in leetcode TC=O(n) and SC=O(N) + O(N) (stack space recrsive)
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
@@eziosan7208 yes that is also fine 👍
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.
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.
24/01/2022...thanks anna....
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);
}
};
THANX IT HELPED
@@DevanshuAugusty ++
Thanking you later.
@@MadhavGupta-fi2tu thanks madhav lord
thx
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?
Why to keep it in an array..you can check that while Traversing the tree
@@AnujYadav-pb5td Yeah, So We can just do that Right?
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.
Shubho Bijaya !!
Diwali te ki DP Series ashbe ?
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
it's not O(1) he's ignoring the recursion stack space O(log(n))
Thanks Man!!!. I was having a hard time understanding this.
Sir , i have a doubt. Can we do it in constant space by morris inorder and checking for each element to be >= previous one .
Is your trees series enough to crack tech giant's interviews like Microsoft linkedin level companies
Yes for trees topic, more than enough!
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
helpful lecture and comments also
this is amazing, thank you!
thank you so much for the explanation
intuitive approach++
Huge respect...❤👏
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);
}
}
crystal clear intuition < 3!!!!
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
At node 12 ,range should be [10,INT_MAX] ??time -4:00
what an amazing explaination:)
thankyou
3 lines of code! thanks bro
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;
}
what if i check for every node left max should be less than current node and rightnode should be less than right min.
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)
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
@@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)?
Thank you Bhaiya
If root nodes value was equal to INT_MIN then would this code work. Assume that root don't have left node.
Thank you sir
Striver is best!!!
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
understood
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;
}
What if we use inorder sorted property of bst if at any point sorting is not maintaned we we will return false
You looks like munnawar Faruqui
thanks mate!
understand thanks
To be a BST should the BT should be balanced?
Awesomeeeee!!!!!
Can we do morris traversal and only have lower bound, this will have better complexity
Clone a graph vala video please jaldi upload karna..Our placement process has started in college 😅😅😅
Okay.. trees k bd !!
Understood
sir can we do by checking inorder traversal of bst is sorted or not
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);
}
};
Which compiler is he using
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);
nice
Understood:)
Here are my detailed notes for this question:
garmadon.notion.site/Validate-Binary-Search-Tree-81d9e081d588424691a163570fc48194
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);
}
};
Excellent brother, I was looking for this to avoid edge cases in lc
US
Love your work bro.♥
UNDERSTOOD
This code fails on duplicate value,
what if 1 has left child as 1
Done!
understood.
*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);
}
range will be problem here
Nice
Thanks
#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);
}
};
❤❤❤
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);
}
};
Bhi, diwali pe DP series ayega kya?
DP series won't come #false_hopes
huge respect❤
bro code link is of checkBST can u put right code link
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;
}
};
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
when i submit it says wrong ans :|
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
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
done!
nice !!