First approach is naive. But it gives an awesome understanding of how recursion works in trees for a complete beginner. The O(n) approach uses range concept which exploits the beautiful properties of a BST.
Another approach could be storing the inorder traversal of BT in a temp array and check if the array is sorted in increasing order. If yes, then its a BST.
@iRock he mentioned that at the end of the video. Also there is no need to recheck if the array is sorted or not. While traversing the tree to get that inorder list, then itself you can do some hack(like he mentioned) to check if the arriving numbers are in sorted order or not. Your comment is 4 years old and you are probably more of an expert right now. However putting this here in case someone else comes here. @Adarsh I think even queue is not needed. In fact no extra data structure is needed. While we are getting the next in-order traversal number, we can simply check if it is greater than or equal to previous value. So we only need to keep track of two int values. ... I think :P
@Jacob Raffe Although I agree with your point that it will add up an extra step, but the time complexity will still be O(n) as O(n+n)=O(2n)=O(n). Yeah, the space complexity will be O(n) in this case, that's something to worry about.
In case this helps others:--- The last approach will not work (in some test cases) if the tree contains INT_MAX or INT_MIN (i.e. 2147483647 or -2147483648) In cases like (following are tree representations) : [2147483647] [-2147483648,null,2147483647] [2147483647,2147483647]
Your explanation is so awesome and understandable. The first approach seems naive but it's so basic and original for a beginner before approaching the second way.
Correction in one of the code snippet at 14:42 if(root->data < minValue && root->data > maxValue... CORRECTION==> if(root->data > minValue && root->data < maxValue...
Great job. Every explanation to this problem I've seen so far explains why the code works. This is the only one that explains how to intuitively and iteratively arrive at the solution one step at a time.
The very first thing that came to my mind for knowing if it is a Binary Search Tree or not was inorder traversal and check whether it is in sorted order or not. =D
inorder traversal of a tree will give values in increasing order if it is BST. Have one variable as prev value to compare with current value, return false if prev
There is a glitch in the final code in the if condition, if(root->data < minValue && root->data > maxValue) && ...) should be if(root->data > minValue && root->data < maxValue) && ...)
You could do this two ways. #1: They are arbitrary values based on the tree you're dealing with. I.e. if the smallest value in my tree is 0, and the greatest is 100, I would initialize MIN = 0 & MAX = 100. #2: As shown in the video, they are macros (aka they need to be included). To do so, just do #include at the top of the file to include the two global vars Hope that helps.
I understand the that we have written the base case for the recursion is, if(root == NULL) return true; But what if the tree is actually NULL, then it'll not check if it's a BST or not it'll simple return true even though there's no Node in the tree.
bro what u did is actually correct...no need of annotation at 14:50. Because u r sending INT_MAX(say 99) and INT_MIN(say -99) via IsUtil function but storing them in the variables (names of which makes u think that u r passing them inversely but actually u r not) so the logic in if Condition in IsUtil is perfect. There isn't a glitch in it.
Good explanation... But second algorithm in which by using of bounds we are just checking next level only so in case of figure "b" which you have seen in starting minutes of this video.... This algorithm gives wrong answer. Because 11 is obviously greater than 7 and less than INT_MAX but it is less than 10...
Okay, so first of all many thanks for the videos. These videos are turning me into a better CS undergrad, for sure. I have a question. Since, the objective of the program is to check if a binary tree is binary search tree or not, we must first have a binary tree. That means we'll have to create one. As I've only been following this series all the way from beginning, I know of only one way to insert elements in tree. But that way ensures that all the members in left subtree are less than or equal to those in right subtree. So just by inserting the elements in main function I end up creating a binary search tree. So basically, my program checks if a binary search tree is a binary search tree and therefore always returns true. I need to know how do I create a binary tree that is not strictly a BST, so that just by creating a tree I do not ensure that the tree is a binary search tree. Thank you for taking out time to read! EDIT: The problem is solved now.
Python Solution Using In-Order (Depth-First) Traversal Note: There is no need to build the entire sorted array as you traverse. Doing that would make memory requirements grow to the order O(n). Only the last seen value in the traversal is stored and compared with the current node being looked at. import sys class Node: def __init__(self,data): self.data = data self.left = self.right = None class BST: def __init__(self): self.rootNode = None #default value for variable used to store last-seen minimum value self.min = -sys.maxsize - 1 def CheckTree(self,Node): if not Node: return #first check left child recursively self.CheckTree(Node.left) #then compare current node vale to last seen minimum value if Node.data
Code in Java: /** * Finds if a tree is bst or not. * @param parent the main root node from the callee method * @param minRange negative infinity: to check on the left subtree. * if all the subtree is lesser or equal than the parent. * @param maxRange positive infinity: to check on the right subtree. * if all the subtree is greater than the parent. * @return true or false * Note: basically changing of the maxRange and minRange will give us result. * Left Subtree must be lesser than the root value (-infinity = minRange && parent.data < maxRange && isBST(parent.left,minRange,parent.data) // checking each of the subtree recursively. && isBST(parent.right, parent.data, maxRange) ) { return true; } return false; }
Need clarification for 1st algorithm - Why is there a need to recursively call the function in isSubTreeLesser and isSubTreeGreater when we are making a recursive call in the isBinarySearchTree function. As if noticing intuitively we can keep checking in the same sequence of operations as the insert operation. So, for every node we just need to check whether it's left is less than or equal to, and right is greater or not. And then recursively call the function for Both Subtrees. There is no need to traverse the tree again and again.
Hi, I have used your solution checking if data lies bet -INF and INF technique. The same code you have posted in the video. But, it doesn't pass all the test cases in Leetcode. May I know why?
The above code will fail if we have element 5 in place of element 1. The recursive call to ISL will be ISL(180,7) and since 5 < 7 the function will return true, however it is not a Binary search tree because 5 is greater than its parent 4 and is still its left child. IN the function IsSubtreeLess() the recursive call to itself should be IsSubtreeLess(root->left,root->data) and IsSubtreeLess(root->right ,root->data)
There is one situation when this code will not work. If you have one node and this node value is equal to the MIN or MAX of integer. But explanation is awesome
Hello, thanks for the video, it's very helpful. However, I want to consult with you your second approach. I think it could fail with this binary tree: 5 / \ 2 null / \ null 6
There is an edge case where this fails. When certain keys in the tree = max value of an int or min value of an int Ex: A tree with only one Node Root | ------------------------------------------ | null | 2147483647 | null | ------------------------------------------ returns false instead of true.
This should be the function for the code to allow duplicates in the BST. Correct me if I am wrong. bool isBinarySearchTree(node *root, int minValue, int maxValue) { if(root==NULL){ return true; } if( root->data>minValue && root->dataleft, minValue, root->data) && isBinarySearchTree(root->right, root->data, maxValue) ){ return true; } return false; }
in the first solution, isBinarySearchTree need not be called again recursively as the first two conditions inherently make sure that the subtree is a bst. am I wrong?
very good explanation, sir why don't you explain avl,red black trees, graphs representations,graph traversals,heaps,hash tables and advanced data structures
In 6:30 How can I find the max and min of a binary tree if I'm not sure whether it is a BST or not? If it's a BST I can simply traverse left subtree to find min, but in the case of general binary tree, what can I do?
My IsBST() function using Inorder: bool IsBST(BST_Node* root){ int temp = 0; int temp2 = 0; if (root==NULL){ return true; } IsBST(root->left); temp = root->data; //temp - current value from function call - MUST be > prev if ( temp2 > temp ){ //temp2 - previous value from function call return false; } temp2 = temp; IsBST(root->right); }
I'm just being a bit picky, but at the end, instead of changing the function name and making a new function, couldn't you have just set a default value? In other words, you could have done bool IsBinarySearchTree(Node* root, int minValue = INT_MIN, int maxValue = INT_MAX){ code} instead of making the two parameters required?
in case if you're wondering about doing this, but by using in order traversal, here is the code: bool isbst(Node *root) { static int prev = INT_MIN; if (root == NULL) return true; return isbst(root->left); if (!(root->data > prev)) { return false; } prev = root->data; return isbst(root->right); }
Thanks for the video and good explanation. But as already noted by some, this solution doesn't work when Node with integer max value is used (won't pass Leet code test). The solution below will take care of that (C#). public bool IsValidBST(TreeNode root) { return IsValidBSTInternal(root,null,null); } public static bool IsValidBSTInternal(TreeNode root, TreeNode minNode, TreeNode maxNode) { if(root==null) return true; if((minNode!=null && root.val = maxNode.val)) return false; else return IsValidBSTInternal(root.left,minNode,root) && IsValidBSTInternal(root.right,root,maxNode); }
It depends on the data that's inside. If they are ints, you might take max and min int as suggested in video. If you think that is not sufficient, you can always look for min and max before. You would need to traverse throught tree once (depth first or breadth first search ), which you can do in O(n) time, so to do this before checking if it's binary, your time copmlexity would be O(2n) which in fact is still O(n). So it's not that bad. But in most cases, you can just think a little and just choose min and max that will be sufficient for you data set.
-INF would be the minimum value that you can store in your variable. +INF would be the maximum that you can store in your variable. In 32 bit signed int, you can store values from -2^31 to (2^31-1),,, INT_MIN is a macro/constant in limits.h header that gives us the minimum value that can be stored in "int" type. Similarly INT_MAX gives us the maximum value. Watch this video to understand things better - Know your data type: int - C Programming Tutorial 08
if there was "8" in place of 6 , wouldnt the 2nd solution fail? 8 would be less than INT_MAX , and code would return true. if 8 was there in place of 6,it wouldnt be a BST right?
yes . but then the space complexity will be O(n). To overcome that , we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST. (I like this inorder approach rather than min max)
hey there ,dont you think that in case when there is 5 in place of 1 then also the 1 method gives the answer true?? because islesser function takes the value of the root node only but we should have to compare it with the value of root node of that subtree only......please explain
To allow duplicates, is it ok if in the condition check in the IsBstUtil() function i make just one little tweak...viz. instead of : if((root->data > minValue) && (root->data < maxValue) && ...etc...etc) i do .. if((root->data > minValue) && (root->data
First approach is naive. But it gives an awesome understanding of how recursion works in trees for a complete beginner. The O(n) approach uses range concept which exploits the beautiful properties of a BST.
At 14:49, it should be root->data > minValue && root->data < maxValue.
Anyway another great video.
Manak Upadhyay yes I was wondering the same.i think you re right
you are right, same here
Yes, I was going to Comment the Same thing.....!!!!!
@@anjalidarokar2408 yup, same here.
realizing it after your comment
Another approach could be storing the inorder traversal of BT in a temp array and check if the array is sorted in increasing order. If yes, then its a BST.
why temp array why not queue
@iRock he mentioned that at the end of the video. Also there is no need to recheck if the array is sorted or not. While traversing the tree to get that inorder list, then itself you can do some hack(like he mentioned) to check if the arriving numbers are in sorted order or not. Your comment is 4 years old and you are probably more of an expert right now. However putting this here in case someone else comes here.
@Adarsh I think even queue is not needed. In fact no extra data structure is needed. While we are getting the next in-order traversal number, we can simply check if it is greater than or equal to previous value. So we only need to keep track of two int values.
... I think :P
that would take a lot of memory, that's a problem
@Jacob Raffe Although I agree with your point that it will add up an extra step, but the time complexity will still be O(n) as O(n+n)=O(2n)=O(n). Yeah, the space complexity will be O(n) in this case, that's something to worry about.
tyyyyy
I like how you went in detail with each recursive call. Great video bro!
In case this helps others:---
The last approach will not work (in some test cases) if the tree contains INT_MAX or INT_MIN (i.e. 2147483647 or -2147483648)
In cases like (following are tree representations) :
[2147483647]
[-2147483648,null,2147483647]
[2147483647,2147483647]
But he mentions strictly about integers not is general, right? Do u know how to do it in a general form coz I am confused
Yup, Leetcode won't accept this solution
Your explanation is so awesome and understandable. The first approach seems naive but it's so basic and original for a beginner before approaching the second way.
A simpler way would be to make an array using Inorder Traversal and check if it is sorted or not... Sorted will mean it is a BST
Thank you!! This was the way to go!
2:10 we have boolean type in C #include
really?
super way to teaching, every single tutorial is so crisp and easy to understand.
Correction in one of the code snippet at 14:42
if(root->data < minValue && root->data > maxValue... CORRECTION==> if(root->data > minValue && root->data < maxValue...
yeah! found the same
@Milind Walekar
Do not answer back to your elders.
Bad Sanskar..
exactly!
@@qR7pK9sJ2t You're funny!
Please upload videos on interview questions like dynamic programming
Great job. Every explanation to this problem I've seen so far explains why the code works. This is the only one that explains how to intuitively and iteratively arrive at the solution one step at a time.
In case, you have duplicates in your tree use root->data >= min && root->data
The very first thing that came to my mind for knowing if it is a Binary Search Tree or not was inorder traversal and check whether it is in sorted order or not. =D
+ANSHU KUMAR it makes sense. :D
+ANSHU KUMAR This will take O(N) time, which is great, but also O(N) space.
+Mohit Ranka instead of printing values in array, we could use 2 variables to just compare the values out of inorder traversal and save O(N) space.
how can we use a variable and make it retain the previous max when recursion is involved?
@@MrBunny53 may be use a global variable?
inorder traversal of a tree will give values in increasing order if it is BST. Have one variable as prev value to compare with current value, return false if prev
There is a glitch in the final code in the if condition,
if(root->data < minValue && root->data > maxValue) && ...)
should be
if(root->data > minValue && root->data < maxValue) && ...)
Kumar Sadhu Yeah, in earlier parts its correct, but later it is incorrect. Thanks for noticing.
hello, how to define -infinity and infinity?
You could do this two ways.
#1: They are arbitrary values based on the tree you're dealing with. I.e. if the smallest value in my tree is 0, and the greatest is 100, I would initialize MIN = 0 & MAX = 100.
#2: As shown in the video, they are macros (aka they need to be included). To do so, just do #include at the top of the file to include the two global vars
Hope that helps.
how we can use MIN n Max in this function
Not sure what you mean? Did you watch the video? - Are you asking specifically from the video? Or, is this a separate question?
We can also have in-order traversal and check whether the current data is greater than or equal to previous data.
The best video on youtube for data structures
Code for checking BST by doing inOrder Traversal only:-
bool checkBST(Node* root) {
static int prevData = -999;
static bool flag = true;
if(root){
checkBST(root->left);
if(root->data > prevData && flag==true){
flag = true;
prevData = root->data;
checkBST(root->right);
return flag;
}
else{
flag = false;
return flag;
}
}
return flag;
}
Nice technique bro
The range for the second solution @15:00 should be:
root->data > minValue && root->data
minValue is for right bst & maxValue is for left, so min of right>root->data & max of left data.
so given is correct.
I understand the that we have written the base case for the recursion is,
if(root == NULL) return true;
But what if the tree is actually NULL, then it'll not check if it's a BST or not it'll simple return true even though there's no Node in the tree.
Instead of making IsBstUtil you can also use default paramters
My solution based on In-Order method:
bool IsInOrder(BTNode* node, int* &var){
if (node == nullptr){
return true;
}
else{
return (IsInOrder(node->left, var) && (*var data) && (*var = node->data) && IsInOrder(node->right, var));
}
}
bool IsBinarySearchTree3(BTNode* node){
int num = INT_MIN;
int *var = #
return IsInOrder(node, var);
}
bro what u did is actually correct...no need of annotation at 14:50. Because u r sending INT_MAX(say 99) and INT_MIN(say -99) via IsUtil function but storing them in the variables (names of which makes u think that u r passing them inversely but actually u r not) so the logic in if Condition in IsUtil is perfect. There isn't a glitch in it.
Good explanation... But second algorithm in which by using of bounds we are just checking next level only so in case of figure "b" which you have seen in starting minutes of this video.... This algorithm gives wrong answer.
Because 11 is obviously greater than 7 and less than INT_MAX but it is less than 10...
Okay, so first of all many thanks for the videos. These videos are turning me into a better CS undergrad, for sure.
I have a question.
Since, the objective of the program is to check if a binary tree is binary search tree or not, we must first have a binary tree. That means we'll have to create one. As I've only been following this series all the way from beginning, I know of only one way to insert elements in tree. But that way ensures that all the members in left subtree are less than or equal to those in right subtree. So just by inserting the elements in main function I end up creating a binary search tree. So basically, my program checks if a binary search tree is a binary search tree and therefore always returns true.
I need to know how do I create a binary tree that is not strictly a BST, so that just by creating a tree I do not ensure that the tree is a binary search tree.
Thank you for taking out time to read!
EDIT: The problem is solved now.
Can you share how you solved your problem?
I have the same issue..kindly share it here
#include
#include
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *addNode(int data)
{
struct node *new = (struct node *)malloc(sizeof(struct node));
new->data = data;
new->left = NULL;
new->right = NULL;
return new;
}
void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(struct node *root)
{
if (root != NULL)
{
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
void inOrder(struct node *root)
{
if (root != NULL)
{
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
int main()
{
struct node *root = addNode(2);
struct node *t1 = addNode(5);
struct node *t2 = addNode(6);
struct node *t3 = addNode(9);
struct node *t4 = addNode(8);
struct node *t5 = addNode(1);
root->left = t1;
root->right = t2;
t1->left = t3;
t1->right = t4;
t2->right = t5;
/*the tree is reprsented below
2
/\
5 6
/\ \
9 8 1
*/
preOrder(root);
printf("
");
postOrder(root);
printf("
");
inOrder(root);
return 0;
}
now you do not know if its a BST or NOT
Time complexity of first program is O(V^2+E^2)
Python Solution
Using In-Order (Depth-First) Traversal
Note: There is no need to build the entire sorted array as you traverse. Doing that would make memory requirements grow to the order O(n).
Only the last seen value in the traversal is stored and compared with the current node being looked at.
import sys
class Node:
def __init__(self,data):
self.data = data
self.left = self.right = None
class BST:
def __init__(self):
self.rootNode = None
#default value for variable used to store last-seen minimum value
self.min = -sys.maxsize - 1
def CheckTree(self,Node):
if not Node:
return
#first check left child recursively
self.CheckTree(Node.left)
#then compare current node vale to last seen minimum value
if Node.data
The max value for 6 is the root's value, right? but the max is not changed when comparing 6, so 6 is comparing with infinity not 7?
Thank you for helping out my homework... I can do it in O(n^2) but not O(n). Very helpful video!
I think it should be 0(log n) instead
Code in Java:
/**
* Finds if a tree is bst or not.
* @param parent the main root node from the callee method
* @param minRange negative infinity: to check on the left subtree.
* if all the subtree is lesser or equal than the parent.
* @param maxRange positive infinity: to check on the right subtree.
* if all the subtree is greater than the parent.
* @return true or false
* Note: basically changing of the maxRange and minRange will give us result.
* Left Subtree must be lesser than the root value (-infinity = minRange && parent.data < maxRange
&& isBST(parent.left,minRange,parent.data) // checking each of the subtree recursively.
&& isBST(parent.right, parent.data, maxRange) ) {
return true;
}
return false;
}
You are doing a really noble work. Please keep it up.............!
I would even recommend to make a series on algorithms.
Need clarification for 1st algorithm -
Why is there a need to recursively call the function in isSubTreeLesser and isSubTreeGreater when we are making a recursive call in the isBinarySearchTree function.
As if noticing intuitively we can keep checking in the same sequence of operations as the insert operation.
So, for every node we just need to check whether it's left is less than or equal to, and right is greater or not. And then recursively call the function for Both Subtrees. There is no need to traverse the tree again and again.
actually, first, he checks with root data then left node value up to leaf node value and then right node value up to leaf node value
Hi, I have used your solution checking if data lies bet -INF and INF technique. The same code you have posted in the video. But, it doesn't pass all the test cases in Leetcode. May I know why?
...Just in order traversal. O(n) runtime, and way more intuitive. If result is not in ascending order, then we know it's not a bst.
The above code will fail if we have element 5 in place of element 1. The recursive call to ISL will be ISL(180,7) and since 5 < 7 the function will return true, however it is not a Binary search tree because 5 is greater than its parent 4 and is still its left child.
IN the function IsSubtreeLess() the recursive call to itself should be IsSubtreeLess(root->left,root->data) and IsSubtreeLess(root->right ,root->data)
It actually won't. I get's filtered out during IBST(150), which gets called later IBST(200). So, it will return false in IBST(150)
There is one situation when this code will not work. If you have one node and this node value is equal to the MIN or MAX of integer. But explanation is awesome
Hello, thanks for the video, it's very helpful.
However, I want to consult with you your second approach.
I think it could fail with this binary tree:
5
/ \
2 null
/ \
null 6
absolutely . even i had the same doubt. i wonder how come no one has addressed this
@@vasantprabhu this isn't a BST 6>5
Hey mycodeschool , at 14:22, in the second if condition, shouldn't it be root->data
@mycodeschool , this should be a small typo
very nice! but space complexity and time complexity can be discussed in detail as well
Holy f***K what a good recurssion logic!!!!!!
IMPRESSIVE
Thanks for the awesome video :)
@14:45 root->data should be > minValue ????
and root->data should be < maxValue :P Small mistake, please forgive him :D
There is an edge case where this fails. When certain keys in the tree = max value of an int or min value of an int
Ex: A tree with only one Node
Root
|
------------------------------------------
| null | 2147483647 | null |
------------------------------------------
returns false instead of true.
thank you mr. india, helped me alot.
This should be the function for the code to allow duplicates in the BST. Correct me if I am wrong.
bool isBinarySearchTree(node *root, int minValue, int maxValue)
{
if(root==NULL){
return true;
}
if( root->data>minValue && root->dataleft, minValue, root->data)
&& isBinarySearchTree(root->right, root->data, maxValue) ){
return true;
}
return false;
}
in the first solution, isBinarySearchTree need not be called again recursively as the first two conditions inherently make sure that the subtree is a bst. am I wrong?
very good explanation, sir why don't you explain avl,red black trees, graphs representations,graph traversals,heaps,hash tables and advanced data structures
All good but it fails certain test cases if you used integer min and max values. my advice would be to use long values instead
Once you should traverse it for non-bst ....I think the code will fail ....put 5 in place of 1.
@10:45 isBinarySearchTree function
why not inorder traversal?
HE DID MENTION IT
In 6:30
How can I find the max and min of a binary tree if I'm not sure whether it is a BST or not?
If it's a BST I can simply traverse left subtree to find min, but in the case of general binary tree, what can I do?
int FindMax(BstNode* root){
if(!root) return INT_MIN;
int max_node = root->data;
max_node = max(max_node, FindMax(root->left));
max_node = max(max_node, FindMax(root->right));
return max_node;
}
int FindMin(BstNode* root){
if(!root) return INT_MAX;
int min_node = root->data;
min_node = min(min_node, FindMin(root->left));
min_node = min(min_node, FindMin(root->right));
return min_node;
}
Using inorder traversal and checking that we are visiting all the nodes in a sorted manner.
bool InorderUpdated(Node *root , int &prevValue)
{
if(root == NULL) return true;
if( InorderUpdated(root->left , prevValue)== false)
return false ;
if(prevValue > root->data)
return false ;
prevValue = root->data ;
if( InorderUpdated(root->right , prevValue)== false)
return false ;
return true ;
}
bool IsBinarySearchTree(Node *root) {
if(root == NULL) return true;
int prevValue = INT_MIN ;
return InorderUpdated(root , prevValue) ;
}
Sir how the time complexity of first method is n^2?
Thank you so much for these videos. Helping me tremendously.
My IsBST() function using Inorder:
bool IsBST(BST_Node* root){
int temp = 0;
int temp2 = 0;
if (root==NULL){
return true;
}
IsBST(root->left);
temp = root->data; //temp - current value from function call - MUST be > prev
if ( temp2 > temp ){ //temp2 - previous value from function call
return false;
}
temp2 = temp;
IsBST(root->right);
}
Saša Škvorc doesn't worked
I'm just being a bit picky, but at the end, instead of changing the function name and making a new function, couldn't you have just set a default value? In other words, you could have done bool IsBinarySearchTree(Node* root, int minValue = INT_MIN, int maxValue = INT_MAX){ code} instead of making the two parameters required?
Please make videos on dynamic programming also
INT_MAX and INT_MIN should be reversed while function call in IBST right ? It is wrong in the video?
Perfect Explanation
in case if you're wondering about doing this, but by using in order traversal, here is the code:
bool isbst(Node *root)
{
static int prev = INT_MIN;
if (root == NULL)
return true;
return isbst(root->left);
if (!(root->data > prev))
{
return false;
}
prev = root->data;
return isbst(root->right);
}
Can we check if a BT is BST or not by just traversing whole BT inorederly and then comparing elements? Both the solutions have O(n) complexity.
sir, please can you make lectures on graph algorithms
Swathi K they are already there....
Nice explaination!!!
For duplicates just equal to( =) sign is enough while comparing with minvalue and max value???
the C way of comparison
nice explanation and inorder technique is great!!
Nice explanation sir. please upload algorithms of heapUp and heapDown, build heap and implementation also.
thank you.
awesomely explained..
Love how you pronounce "greater" in 1.75x speed😂. btw keep it up, love watching your videos.
In the second approach, when we have defined ranges for each node's value, why do we again need to check it the subtree is a valid BST or not?
INORDER METHOD:
bool isBST(struct node* root){ static struct node *prev = NULL; // traverse the tree in inorder fashion and keep track of prev node if (root) { if (!isBST(root->left)) return false; // Allows only distinct valued nodes if (prev != NULL && root->data data) return false; prev = root; return isBST(root->right); } return true;}
For recursion is this code work properly? I tried many times but it wasn't working. Anybody has a solution using recursion?
Thanks for the video and good explanation. But as already noted by some, this solution doesn't work when Node with integer max value is used (won't pass Leet code test). The solution below will take care of that (C#).
public bool IsValidBST(TreeNode root) {
return IsValidBSTInternal(root,null,null);
}
public static bool IsValidBSTInternal(TreeNode root, TreeNode minNode, TreeNode maxNode)
{
if(root==null) return true;
if((minNode!=null && root.val = maxNode.val))
return false;
else
return IsValidBSTInternal(root.left,minNode,root) && IsValidBSTInternal(root.right,root,maxNode);
}
But this only works when the duplicates are not allowed. Isn't it? Please clarify.
last approach is failing if the value of nodes are themselves INT_MIN && INT_MAX...
Hi guys, here is my example
bool isBST(Node* root)
{
if(NULL == root)
{
return true;
}
if((NULL == root->left || root->data >= root->left->data) &&
(NULL == root->right || root->data < root->right->data) &&
isBST(root->left) &&
isBST(root->right))
{
return true;
}
return false;
}
Konstantin Beluchenko Best soln
Konstantin Beluchenko does this catch case B at 1:12?
+Sergei Anonymoff You are absolutely correct, It doesn't catch that case!
Shouldn't the time complexity of the recursive algorithm be O(nlogn) by master theorem?
Great Video sir.
Can someone check my answer, is this correct code for the third method?
/* Method 3 - Inorder traversal - O(n) - duplicates allowed */
bool IsBSTUtil2(Node* root, int lastValue);
bool IsBinarySearchTree3(Node * root){
int lastValue;
return IsBSTUtil2(root, root->data);
}
bool IsBSTUtil2(Node* root, int lastValue){
if(root == NULL)
return true;
IsBSTUtil2(root->left, lastValue);
if(root->data >= lastValue)
lastValue = root->data;
else
return false;
IsBSTUtil2(root->right, lastValue);
return true;
}
Sir u are amazing
It is really helpful
I couldn't understand why a different function was required to call the original function in the second solution.
+mycodeschool Can we not give default arguements instead of writing one more function?
how to decide the values of INT_MIN & INT_MAX like you said it should be -inf and +inf but how to put these values in the program.
It depends on the data that's inside. If they are ints, you might take max and min int as suggested in video.
If you think that is not sufficient, you can always look for min and max before. You would need to traverse throught tree once (depth first or breadth first search ), which you can do in O(n) time, so to do this before checking if it's binary, your time copmlexity would be O(2n) which in fact is still O(n). So it's not that bad.
But in most cases, you can just think a little and just choose min and max that will be sufficient for you data set.
-INF would be the minimum value that you can store in your variable. +INF would be the maximum that you can store in your variable. In 32 bit signed int, you can store values from -2^31 to (2^31-1),,, INT_MIN is a macro/constant in limits.h header that gives us the minimum value that can be stored in "int" type. Similarly INT_MAX gives us the maximum value. Watch this video to understand things better - Know your data type: int - C Programming Tutorial 08
@@mycodeschool Thanks A lot...……. May you be happy Always.....
What is the complexity of first approach?
Thank you. very clear lesson and great for refresher!
Super understanding...
why we need to make another function when we already had BSTutil() method?
if there was "8" in place of 6 , wouldnt the 2nd solution fail? 8 would be less than INT_MAX , and code would return true. if 8 was there in place of 6,it wouldnt be a BST right?
only the longer solution number 1 is accurate , where each node is compared with every other node in its subtree
Good video! Thank you
in second approach of minvalue and maxvalue how we will analyse that left subtree and right subtree is BST or not?
Bro we need to check the condition for every node by finding min and Max value
Can we judge by sorted array and inorder of the binary search tree?
yes . but then the space complexity will be O(n). To overcome that , we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST. (I like this inorder approach rather than min max)
very interesting algorithms
can someone write the code please
one funny fact is that it doesn't matter how many times I implement this program on my compiler anyway i am gonna get THIS IS A BINARY SEARCH TREE
Sir i need code to check whether a tree is a BST or not by In-order traversal method as u have mentioned in the video to check mine code.
hey there ,dont you think that in case when there is 5 in place of 1 then also the 1 method gives the answer true??
because islesser function takes the value of the root node only but we should have to compare it with the value of root node of that subtree only......please explain
Notice that he is making recursive calls to left and right subtrees of every node i.e., ibst(root->left) and ibst(root->right) :)
why would bother with min and max values ?
bool IsBinary2 (Node* root)
{
if (root == NULL || root->left ==NULL || root->right == NULL)
return true;
if (root->left->data < root->data &&
root->right->data> root->data)
{
if(IsBinary2(root->left) && IsBinary2(root->right))
return true ;
}
return false;
}
wow bro you teach so well :) :) :)
How to handle cases of duplicates while checking with in order traversal?
To allow duplicates, is it ok if in the condition check in the IsBstUtil() function i make just one little tweak...viz. instead of :
if((root->data > minValue) && (root->data < maxValue) && ...etc...etc)
i do .. if((root->data > minValue) && (root->data
can we use inorder transverse to check whether binary tree is BST or not?
Yes...Binary Search Tree inorder traversal always in sorted order so you need to check whether your output elements are sorted or not
just use inorder traverasl and keep checki g the preious value
..no need to watch the video