If anyone would like to see a simple Python implementation, check out my recent lesson: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-azupT01iC78.html
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.
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); }
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
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 ?
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?
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)
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); }
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.
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/
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.
