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.
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!
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); }
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)
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?.
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?
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
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?
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 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 ?
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); }
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/
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.
So you are using recursion to solve this problem, and recursion uses call stack! One caveat - this could lead to stack overflow if the tree is ridiculously large.
You are right, John. Recursive approach is vulnerable to stack overflow error. We could use Depth-First or Breadth-First Traversal of the tree which have the same Time cost with same worst case Space Complexity. But, DF is more efficient with O(lgn) or O(d) {d : depth(Tree)} space complexity in best case/average case.
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.
The recursion diagram of running test cases is really really helpful to fix bug, THANK YOU Tushar !
I was struggling with an annoying problem, and your video helped a lot. Thank you so much.
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 table helps a lot to track the recursive calls. Thanks Sir :)
You explained this really well! I had a hard time finding a solution that was easy to understand! Thank you!
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!
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 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);
Best explanation for this question on TH-cam
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
Very clear step by step explanation! Hope to see more videos from you
Good Work Tushar. Thanks for this simple yet elegant explanation.
Thanks, Sir g !! You have clarified recursion stack as well :)
Hi thanks for making smaller videos. Keep making small length videos around ten minutes. And thank you for making videos.
In order traversal plus boost.circular but ffer.of size.2 gives most efficient solution O(n) time complexity and O(1) space complexity
The best video on the internet on this problem
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.
Loved the explanation, esp. table visualization
Best video on internet sir
welcome back to th garage
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 Job Tushar!
Nice video. Really good explanation. if you can try explaining about time complexity as well,then it would be great.
Thanks for sharing !!..After watching 3 videos finally I land on this great one...
Awesome!! Like the way you go through the solution. Thank you so much!
Your code doesn't work in cases where the input is [2147483647] or [-2147483648 ,null, 2147483647]
Fantastic! So simple and elegant!
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 to explain the BST.
I might be late to this thread. But there seems to be an inorder traversal based solution. Would you cover that as well?
during inorder traversal if current node data is lesser than previous data it is not a BST
very good explanation, the best so far
Thanks Tushar! That was super helpful
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?
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
Hey Tushar - guess I bumped into a few edge cases ; in the code - why would we do only root.data
Sir ji maza aha gya smj kar
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?
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 code! Good explanation.
Awesome walkthrough
We can use inorder traversal and checking if current node is greater than global variable set global variable as current else return not bst
shouldn't the time expense be O(h) where h is the height of the tree?
This was a very good explanation.
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.
incredibly explained! thank you!
Well done Gautam Gambhir
Very well explained.Thank you
1Kth like :D.
Thanks for this series btw.
great explanation thanks 👌
That's the greatest explanation in youtube
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 ?
Great video... clear explanations... Thanks a lot
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);
}
excellent explanation
Awesome Explanation. Thanks Bro :-)
Nice one. Really appreciate it.
very well explained! Thank you.
it's a shame that this guy doesn't make videos anymore.
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.
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.
@3:33
WELCOME BACK
to the GARAGE
genial, gracias desde bsas, Argentina :)
Well explained bro, Thank you
What is the space complexity?
what if the the type of tree node is written in template, how to define infinity
Thanks for the video.
Can we some iterative approach to do it ?
so clearly，thank you
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?
Thanks Tushar! I always refer to your explanations when stuck, but this code doesnt work for (1,1,null) :(
Thanks for the video
What is the function "isBSTIterative" for?
Can't assign infinity to a number. How would you actually execute it ?
in C++, we have INT_MAX and INT_MIN inbuilt.
you made look simple. thank you.
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
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
Would you please comment your code on Github? It will be helpful for all the starters. Thanks!
this is PreOrder traversal right?
YOU are the best
nice explanation
Thanks. it was helpful!
he was in Amazon , seatle
Thank you sir , God bless: )
If anyone would like to see a simple Python implementation, check out my recent lesson: th-cam.com/video/azupT01iC78/w-d-xo.html
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.
So you are using recursion to solve this problem, and recursion uses call stack! One caveat - this could lead to stack overflow if the tree is ridiculously large.
Thank you for this wonderful lesson btw :)
You are right, John. Recursive approach is vulnerable to stack overflow error. We could use Depth-First or Breadth-First Traversal of the tree which have the same Time cost with same worst case Space Complexity. But, DF is more efficient with O(lgn) or O(d) {d : depth(Tree)} space complexity in best case/average case.
root.data >= max . I guess you missed the equal-to symbol there.
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.
you are the best :)
Still the best!
can you please try iteration ? Thank you
Iteration is quite hard compared to recursive especially in tree's.
This is not working on [1,1]
Just amazing
May god bless you
Bruh. MIN & MAX won't work if root.val = Integer.MAX_VALUE :(
Hi Tushar, will this work on a BST like [Integer.MIN_VALUE,null,5,null,null,null,8]?
no, it will not work, in this case, you have to use integer object instead of MAX nad MIN and the fact that they are default null.
Thanks sir