Wow, this has helped a lot. The columns you made to step through the recursive calls was a great idea, I'm usually writing stuff all over the place & it just winds up messy & confusing.
exactly, I did not understand why a simple in order traversal will not do here. It is such a simple way to do it. I also get that in the interviews they do not like the in-order approach and that beats me.
we can do a inorder Traversal and store root.value in a List , If the List is sorted in Increasing order , it is a BST . (Simpler solution, but probably higher Space complexity)
Why not to perform inorder traversal of the tree and check simultaneously whether the data is in sorted order or not? If yes,then the tress is BST else not
It can be done in constant space too. Instead of storing all elements, store last element in In-order traversal in a single variable and check every node value to that variable. After every comparison update the variable value to node value. O(1) Space .:-) Java Code : public int min = Integer.MIN_VALUE; // This will be a global variable like min, max referred in the video public boolean isBST(TreeNode root, int min){ if(root == null) return true; boolean left = isBST(root.left,min); if(min >= root.val) return false; min = root.val; boolean right = isBST(root.right,min); return(left && right); }
I don't think it will be slow. Check the below code. Same complexity (time and space); Java Code : public int min = Integer.MIN_VALUE; // This will be a global variable like min, max referred in the video public boolean isBST(TreeNode root, int min){ if(root == null) return true; boolean left = isBST(root.left,min); if(min >= root.val) return false; min = root.val; boolean right = isBST(root.right,min); return(left && right); }
Just one suggestion at 0.17 , left is less than or equal to root(not just less) and right is greater than root. Btw nice video. Look forward to see more such videos. Good going Tushar!
hi Tushar, As usual awesome explanation. However as some of the people have commented, even I was thinking why this cannot be achieved via In-Order Traversal? It will also take O(n) time and we can manage to compare the values using constant space. Can you please explain if this method is still efficient than In-Order traversal?
Big Thank you for cool execution flow illustration . I've best understood with your illustration but not agree with your example and code . PS :: Do Share your view point to below query . Query : Property says : " The left subtree of a node contains only nodes with keys less than the node’s key and Each node (item in the tree) has a distinct key. " Your example have 10 in left subtree same as value of root (10), What if we take 10 again instead of -5 , as per your flow in code it will pass and we will have duplicate values in BST . (Because 10 is again not large than max(10) but equal to 10 as per explained by you in second iteration .) I agree with GKG that to tighten up boundaries we can use following conditions : /* false if this node violates the min/max constraints */ if (node.data < min || node.data > max) return false; /* otherwise check the subtrees recursively tightening the min/max constraints */ return (isBSTUtil(node.left, min, node.data-1) && isBSTUtil(node.right, node.data+1, max)); // Allow only distinct values Ref : www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
Thank you very much, Tushar!. I had a thought on this, can't we just go InOrderTraversal keep adding to a list/array for instance and then check if the list/array is sorted?.
Thanks for the solution.. whats the space complexity of this ? would it be O(height of tree) since we are using those many nodes on stack for recursion
The base thinking is ok. But there are some bugs in your solution. First there no anything condition need for root.val, is don't need be larger than Integer.MIN_VALUE, it can be Integer.MIN_VALUE. And it can be Integer.MAX_VALUE. You introduce an unnecessary condition into this problem. The right solution is to use null to avoid unnecessary condition. Like this: public boolean isValidBST(TreeNode root) { return isBST(root,null,null); } private boolean isBST(TreeNode node,Integer min,Integer max) { if (node==null) return true; if(min!=null && node.val=max) return false; return isBST(node.left,min,node.val) && isBST(node.right,node.val,max); }
I understand that the worst-case runtime of this algorithm is O(N), however, is it true to say that in the case of it NOT being a binary search tree, the runtime would be O(N/2), since once one of the subtrees returns false, there's no need to check the other half of the tree, since FALSE && TRUE is already determined to be false?
This binary tree traversing is PreOrder OR Inorder. Can we implement same logic with different traversing (InOrder/PostOrder) ,if yes ,will it be impact on algo complexity ?
Will Inorder traversal work? I mean to keep that last element and to compare with next and so on. Inorder traversal will give us the elements in ascending order so we compare if( last
This algo doesn't work on all test cases :( tried it on leetcode. for example when a tree has only one node and its value is equal to Integer.MAX_VALUE.
You have read it wrong Tushar, the condition if(root.datamax) it's an OR condition, you are saying it as AND condition while speaking, which may confuse some people initially.
Just a suggestion-It would be better if you also show us the working of the algorithm when the example DOESN'T satisfy the condition asked in the question.I mean for this question,it would've been better if you also showed how this algorithm worked for a binary tree which is NOT as bst.
Wow, you're walk-throughs are the best I've found on ds & as. Thanks! keep up the excellent work.
Wow, this has helped a lot. The columns you made to step through the recursive calls was a great idea, I'm usually writing stuff all over the place & it just winds up messy & confusing.
Just do an inorder traversal and keep updating two consecutive values. the moment they are out of order is when you declare False.
Fine but what if you want Left to contain less than or EQUAL to as well
1
/
1 is OK
but not
1
\
1
But in interviews they will ask you different approach not the inorder one.
@@piyushmajgawali1611 but BST is, on the left it is root.
exactly, I did not understand why a simple in order traversal will not do here. It is such a simple way to do it. I also get that in the interviews they do not like the in-order approach and that beats me.
that will not handle duplicates well
The recursion diagram of running test cases is really really helpful to fix bug, THANK YOU Tushar !
note：this algorithm assumes 1）there could be duplicate 2）left subtree
in a binary search tree there would never be duplicate, wouldn't be?
@@czerox16 NO
In order traversal plus boost.circular but ffer.of size.2 gives most efficient solution O(n) time complexity and O(1) space complexity
In recursive call, the value passed as min and max should be return isBST(root.left,root.data-1,min)
&& isBST(root.right,max,root.data+1);
Simplicity is the ultimate sophistication.... Simple :)
there is an even simpler algo. perform inorder traversal. if at any stage the current node value is smaller than previous node value it is not BST
The table helps a lot to track the recursive calls. Thanks Sir :)
I was struggling with an annoying problem, and your video helped a lot. Thank you so much.
You explained this really well! I had a hard time finding a solution that was easy to understand! Thank you!
we can do a inorder Traversal and store root.value in a List , If the List is sorted in Increasing order , it is a BST . (Simpler solution, but probably higher Space complexity)
Instead of list just keep track of last element visited and compare next element with that. Same complexity
Good Work Tushar. Thanks for this simple yet elegant explanation.
best video to explain the BST.
Why not to perform inorder traversal of the tree and check simultaneously whether the data is in sorted order or not? If yes,then the tress is BST else not
That's one way to do it but it will be slower than this method.
That'd be O(n) space, this is O(1) space.
It can be done in constant space too. Instead of storing all elements, store last element in In-order traversal in a single variable and check every node value to that variable. After every comparison update the variable value to node value. O(1) Space .:-)
Java Code :
public int min = Integer.MIN_VALUE; // This will be a global variable like min, max referred in the video
public boolean isBST(TreeNode root, int min){
if(root == null)
return true;
boolean left = isBST(root.left,min);
if(min >= root.val)
return false;
min = root.val;
boolean right = isBST(root.right,min);
return(left && right);
}
I don't think it will be slow. Check the below code. Same complexity (time and space);
Java Code :
public int min = Integer.MIN_VALUE; // This will be a global variable like min, max referred in the video
public boolean isBST(TreeNode root, int min){
if(root == null)
return true;
boolean left = isBST(root.left,min);
if(min >= root.val)
return false;
min = root.val;
boolean right = isBST(root.right,min);
return(left && right);
}
Inorder traversal will do the job in a simpler way. Both are O(n) space since recursion (stack) is used.
Just one suggestion at 0.17 , left is less than or equal to root(not just less) and right is greater than root. Btw nice video. Look forward to see more such videos. Good going Tushar!
Best explanation for this question on RUclips
Your code doesn't work in cases where the input is [2147483647] or [-2147483648 ,null, 2147483647]
Sir ji maza aha gya smj kar
Thanks for sharing !!..After watching 3 videos finally I land on this great one...
Very clear step by step explanation! Hope to see more videos from you
Hi thanks for making smaller videos. Keep making small length videos around ten minutes. And thank you for making videos.
Thanks, Sir g !! You have clarified recursion stack as well :)
Loved the explanation, esp. table visualization
Good Job Tushar!
We can use inorder traversal and checking if current node is greater than global variable set global variable as current else return not bst
The best video on the internet on this problem
during inorder traversal if current node data is lesser than previous data it is not a BST
Nice video. Really good explanation. if you can try explaining about time complexity as well,then it would be great.
welcome back to th garage
hi Tushar, As usual awesome explanation. However as some of the people have commented, even I was thinking why this cannot be achieved via In-Order Traversal? It will also take O(n) time and we can manage to compare the values using constant space. Can you please explain if this method is still efficient than In-Order traversal?
I might be late to this thread. But there seems to be an inorder traversal based solution. Would you cover that as well?
Fantastic! So simple and elegant!
Awesome!! Like the way you go through the solution. Thank you so much!
Awesome walkthrough
Big Thank you for cool execution flow illustration . I've best understood with your illustration but not agree with your example and code .
PS :: Do Share your view point to below query .
Query :
Property says : " The left subtree of a node contains only nodes with keys less than the node’s key and Each node (item in the tree) has a distinct key. "
Your example have 10 in left subtree same as value of root (10), What if we take 10 again instead of -5 , as per your flow in code it will pass and we will have duplicate values in BST . (Because 10 is again not large than max(10) but equal to 10 as per explained by you in second iteration .)
I agree with GKG that to tighten up boundaries we can use following conditions :
/* false if this node violates the min/max constraints */
if (node.data < min || node.data > max)
return false;
/* otherwise check the subtrees recursively
tightening the min/max constraints */
return (isBSTUtil(node.left, min, node.data-1) &&
isBSTUtil(node.right, node.data+1, max)); // Allow only distinct values
Ref : www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
yeah I agree, I was also confused, as the code in video suggests there might be duplicates in BST. BTW it has been 5 years tho.
Thank you very much, Tushar!. I had a thought on this, can't we just go InOrderTraversal keep adding to a list/array for instance and then check if the list/array is sorted?.
Yes but it is not space optimal. This is using O(n) storage.
we can iterate through the tree only and check the prev node is smaller than the present node no need for an extra space buddies
Both are O(n) space since recursion (stack) is used
@@EngMohmdNoor We can use an iterative in order traversal, and get O(1) space
Best video on internet sir
very good explanation, the best so far
Well done Gautam Gambhir
excellent explanation
Very well explained.Thank you
Hey Tushar - guess I bumped into a few edge cases ; in the code - why would we do only root.data
incredibly explained! thank you!
Thanks Tushar! That was super helpful
thank you sooo much, i have been banging my head and yo cleared it off.. thank you.. very good explination with good chart on the right side
Thanks for the solution.. whats the space complexity of this ? would it be O(height of tree) since we are using those many nodes on stack for recursion
This was a very good explanation.
great explanation thanks 👌
very well explained! Thank you.
The base thinking is ok. But there are some bugs in your solution. First there no anything condition need for root.val, is don't need be larger than Integer.MIN_VALUE, it can be Integer.MIN_VALUE. And it can be Integer.MAX_VALUE.
You introduce an unnecessary condition into this problem. The right solution is to use null to avoid unnecessary condition. Like this:
public boolean isValidBST(TreeNode root) {
return isBST(root,null,null);
}
private boolean isBST(TreeNode node,Integer min,Integer max) {
if (node==null)
return true;
if(min!=null && node.val=max)
return false;
return isBST(node.left,min,node.val) &&
isBST(node.right,node.val,max);
}
Great video... clear explanations... Thanks a lot
Thanks for the code! Good explanation.
I understand that the worst-case runtime of this algorithm is O(N), however, is it true to say that in the case of it NOT being a binary search tree, the runtime would be O(N/2), since once one of the subtrees returns false, there's no need to check the other half of the tree, since FALSE && TRUE is already determined to be false?
This binary tree traversing is PreOrder OR Inorder. Can we implement same logic with different traversing (InOrder/PostOrder) ,if yes ,will it be impact on algo complexity ?
shouldn't the time expense be O(h) where h is the height of the tree?
genial, gracias desde bsas, Argentina :)
Thanks for the video.
@3:33
WELCOME BACK
to the GARAGE
so clearly，thank you
That's the greatest explanation in youtube
Awesome Explanation. Thanks Bro :-)
you made look simple. thank you.
Nice one. Really appreciate it.
nice explanation
Well explained bro, Thank you
can i just do an inorder traversal and find out if the traversal is sorted or not as inorder traversal of a binary tree is always sorted.
Still the best!
Will Inorder traversal work? I mean to keep that last element and to compare with next and so on. Inorder traversal will give us the elements in ascending order so we compare if( last
It will works. Thats is also O(n) but this is one more efficient.
How come this is more efficient? Please explain.
Couldn't we just do an in order traversal as well with a global variable? Wouldn't that work as well?
May god bless you
it's a shame that this guy doesn't make videos anymore.
he was in Amazon , seatle
Thanks for the video
Thank you sir , God bless: )
What is the space complexity?
YOU are the best
what if the the type of tree node is written in template, how to define infinity
Thanks. it was helpful!
This algo doesn't work on all test cases :( tried it on leetcode. for example when a tree has only one node and its value is equal to Integer.MAX_VALUE.
Just put the min and max to Long.MIN and Long.MAX, it will work on leetcode
What about the case where the tree is [1,null,1] i.e. root node is 1 and right child is 1. According to this logic, output is True
I have the same question. Were you able to make any modifications and get it to work?
Just amazing
1Kth like :D.
Thanks for this series btw.
You have read it wrong Tushar, the condition if(root.datamax) it's an OR condition, you are saying it as AND condition while speaking, which may confuse some people initially.
Thanks Tushar! I always refer to your explanations when stuck, but this code doesnt work for (1,1,null) :(
Can we some iterative approach to do it ?
Thanks sir
If anyone would like to see a simple Python implementation, check out my recent lesson: ruclips.net/video/azupT01iC78/видео.html
What is the function "isBSTIterative" for?
Thank u sir
Would you please comment your code on Github? It will be helpful for all the starters. Thanks!
Just a suggestion-It would be better if you also show us the working of the algorithm when the example DOESN'T satisfy the condition asked in the question.I mean for this question,it would've been better if you also showed how this algorithm worked for a binary tree which is NOT as bst.
Can't assign infinity to a number. How would you actually execute it ?
in C++, we have INT_MAX and INT_MIN inbuilt.
this is PreOrder traversal right?
you are the best :)
best
thankyou!
This is not working on [1,1]
Hello Tushar, I have tried the code of isBT from your git repo and it doesnot seems to be working
If available online, please reply
+Tushar Roy : The code written in java for isBST, it throws some error
great !!!!!!!!!!!!!!!!!!!!!