Check if a binary tree is binary search tree or not
Вставка
- Опубліковано 1 жов 2024
- See complete series on data structures here:
• Data structures
In this lesson, we have written a program in C/C++ to verify whether a given binary tree is binary search tree or not.
For practice problems and more, visit: www.mycodeschoo...
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool
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
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.
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?
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?
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!
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!
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
Please upload videos on interview questions like dynamic programming
2:10 we have boolean type in C #include
really?
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) ;
}
In case, you have duplicates in your tree use root->data >= min && root->data
I like how you went in detail with each recursive call. Great video bro!
Hey mycodeschool , at 14:22, in the second if condition, shouldn't it be root->data
@mycodeschool , this should be a small typo
Holy f***K what a good recurssion logic!!!!!!
IMPRESSIVE
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...
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?
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);
}
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;
}
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
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;}
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
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 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.
Complete code including Inorder Traversal Check
#include
#include
using namespace std;
struct BstNode
{
char data;
BstNode* left;
BstNode* right;
};
queue Q;
BstNode* GetNewNode(char data)
{
BstNode* newnode = new BstNode();
newnode->data = data;
newnode->left = newnode->right = NULL;
return newnode;
}
BstNode* Insert(BstNode* root, char data)
{
if(root == NULL)
{
root = GetNewNode(data);
}
else if(data data)
{
root->left = Insert(root->left, data);
}
else
{
root->right = Insert(root->right, data);
}
return root;
}
void InOrderCheck(BstNode* root)
{
if(root == NULL) return;
InOrderCheck(root->left);
if(root->data >= Q.front())
{
Q.pop();
Q.push(root->data);
}
InOrderCheck(root->right);
}
bool IsBstUtil(BstNode* root, int minvalue, int maxvalue)
{
if(root == NULL) return true;
if(root->data > minvalue && root->data left, minvalue, root->data) && IsBstUtil(root->right, root->data, maxvalue)) return true;
else return false;
}
bool IsBinarySearchTree(BstNode* root)
{
return IsBstUtil(root, INT_MIN, INT_MAX);
}
int main()
{
BstNode* root = NULL;
root = Insert(root, 'F');
root = Insert(root, 'D');
root = Insert(root, 'J');
root = Insert(root, 'B');
root = Insert(root, 'E');
root = Insert(root, 'G');
root = Insert(root, 'K');
root = Insert(root, 'A');
root = Insert(root, 'C');
root = Insert(root, 'I');
root = Insert(root, 'H');
Q.push(0);
InOrderCheck(root);
if(Q.empty()) cout
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
super way to teaching, every single tutorial is so crisp and easy to understand.
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!
Here is a solution with inordertraversal
bool isBinarySearchTree(struct BSTNode** root, int *temp, int *g) {
if (*root == NULL) {
return;
}
if(*g == 0) return false;
isBinarySearchTree(&((*root)->left), temp, g);
if (*temp > (*root)->data) {
*g = 0;
return false;
}
// printf("temp before assigning: %d
", *temp);
*temp = (*root)->data;
// printf("temp after assigning: %d
", *temp);
isBinarySearchTree(&((*root)->right), temp, g);
return true;
}
+Shreyas C what will be the value of temp for first call of your function ?
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
thank you mr. india, helped me alot.
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
why not inorder traversal?
HE DID MENTION IT
Sir how the time complexity of first method is n^2?
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
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;
}
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;
}
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;
}
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.
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)
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?
INT_MAX and INT_MIN should be reversed while function call in IBST right ? It is wrong in the video?
// check if a tree is binary or not
bool checkBinaryTree(Node *tempRootNode)
{
if (tempRootNode == NULL)
return true;
if (tempRootNode->left != NULL)
{
if (tempRootNode->left->data data)
{
checkBinaryTree(tempRootNode->left);
}
else
{
return false;
}
}
if (tempRootNode->right != NULL)
{
if (tempRootNode->right->data > tempRootNode->data)
{
checkBinaryTree(tempRootNode->right);
}
else
{
return false;
}
}
return true;
}
last approach is failing if the value of nodes are themselves INT_MIN && INT_MAX...
ah great...I found it hard to follow first approach while everyone used that.. idk why with so bad complexity.
For recursion is this code work properly? I tried many times but it wasn't working. Anybody has a solution using recursion?
For duplicates just equal to( =) sign is enough while comparing with minvalue and max value???
the C way of comparison
Instead of making IsBstUtil you can also use default paramters
why can't you make a call like so, instead of an intermediate function?
typedef struct BSTNode
{
int data;
struct BSTNode *leftNode;
struct BSTNode *rightNode;
}BSTNode;
BSTNode *rootNode;
@interface BSTNode:NSObject
-(BOOL)isBinarySeachWithRoot:(BSTNode*)rootNode min:(int)min max:(int)max
;
@end
BSTNode *bst = [[BSTNode alloc]init];
[bst isBinarySearchWithRoot:(BSTNode*)rootNode min:(int)INT_MIN max:(int)INT_MAX];
Inorder traversal implementation in javascript, github.com/KrKandula/Algos-and-DS/blob/master/isBST-method2.js
Thank you so much for these videos. Helping me tremendously.
not 100% right
if the node value is INT_MAX or INt_MIN
say TreeNOde* root = new TreeNOde(MAX_INT)
This algorithm will not pass the test
use value less than INT_MAX and greater than INT_MIN.
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;
}
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.
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.
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
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?
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
Once you should traverse it for non-bst ....I think the code will fail ....put 5 in place of 1.
@10:45 isBinarySearchTree function
Hack is best!
just use inorder traverasl and keep checki g the preious value
..no need to watch the video
Time complexity of first program is O(V^2+E^2)
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
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
can someone write the code please
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.
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
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
I couldn't understand why a different function was required to call the original function in the second solution.
I create a code that always make a correct BST LOL
xDD
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.
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.
Worst explanation I have ever seen in UA-cam and also this program will not work for All the cases
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.
why we need to make another function when we already had BSTutil() method?
Please Help. How to deduce max value from left subtree and min value from right subtree
Never mind got it. Just use root->right in left subtree and root->left in right subtree
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.
while compilation its showing INT_MIN and INT_MAX are not declared in scope ?????????????
Call #include library before compilation.
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
Shouldn't the time complexity of the recursive algorithm be O(nlogn) by master theorem?
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) :)
...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.
very good explanation, sir why don't you explain avl,red black trees, graphs representations,graph traversals,heaps,hash tables and advanced data structures
sir, please can you make lectures on graph algorithms
Swathi K they are already there....
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
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
+mycodeschool Can we not give default arguements instead of writing one more function?
What does he mean when he says NULL is just a macro for 0 ?
NULL is used to check if the pointer to the left or right child is empty i hope this cleared your doubts
very nice! but space complexity and time complexity can be discussed in detail as well
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.....
second alternate part is wrong
what if root equal to null is true then it is BST?
awesomely explained..
Love how you pronounce "greater" in 1.75x speed😂. btw keep it up, love watching your videos.
You are doing a really noble work. Please keep it up.............!
I would even recommend to make a series on algorithms.
Perfect Explanation
How to handle cases of duplicates while checking with in order traversal?
in root lesser or greater how second arg is root type
Good video! Thank you
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?