Check if a binary tree is binary search tree or not

[@sumitsaini1601]

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.

[@manakupadhyay]

At 14:49, it should be root->data > minValue && root->data < maxValue. Anyway another great video.

[@marykapodistria7204]

Manak Upadhyay yes I was wondering the same.i think you re right

[@elweonloco]

you are right, same here

[@anjalidarokar2408]

Yes, I was going to Comment the Same thing.....!!!!!

[@daredevil6145]

@@anjalidarokar2408 yup, same here.

[@kausachan4167]

realizing it after your comment

[@mrmca1]

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.

[@adarshsaavarn6463]

why temp array why not queue

[@blasttrash]

@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

[@saptarshisengupta5073]

that would take a lot of memory, that's a problem

[@himan7196]

@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.

[@lasyagajavelli594]

tyyyyy

[@allenllewellynkra]

I like how you went in detail with each recursive call. Great video bro!

[@codestorywithMIK]

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]

[@anuragumale3013]

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

[@RushOrbit]

Yup, Leetcode won't accept this solution

[@manishkumar1450]

super way to teaching, every single tutorial is so crisp and easy to understand.

[@pradeepbalasundaram]

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.

[@rahul-patil]

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...

[@squillace91]

yeah! found the same

[@qR7pK9sJ2t]

@Milind Walekar Do not answer back to your elders. Bad Sanskar..

[@akhiladiga9771]

exactly!

[@ishumba]

@@qR7pK9sJ2t You're funny!

[@chayakumarsedutainment4799]

2:10 we have boolean type in C #include

[@1Maestr00o3]

really?

[@music-on7507]

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.

[@KumarSadhu]

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) && ...)

[@mycodeschool]

Kumar Sadhu Yeah, in earlier parts its correct, but later it is incorrect. Thanks for noticing.

[@mohitbv2331]

hello, how to define -infinity and infinity?

[@merlinsxbeard]

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.

[@trabelsieya2946]

how we can use MIN n Max in this function

[@merlinsxbeard]

Not sure what you mean? Did you watch the video? - Are you asking specifically from the video? Or, is this a separate question?

[@ajaydattatray6433]

The best video on youtube for data structures

[@deepakjain5101]

Please upload videos on interview questions like dynamic programming

[@ambershekhar8106]

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

[@RushOrbit]

Thank you!! This was the way to go!

[@ANSHUKUMARanish]

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

[@monicaslv323]

+ANSHU KUMAR it makes sense. :D

[@mohitranka9840]

+ANSHU KUMAR This will take O(N) time, which is great, but also O(N) space.

[@sivasarath1063]

+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.

[@MrBunny53]

how can we use a variable and make it retain the previous max when recursion is involved?

[@CSharpBar]

@@MrBunny53 may be use a global variable?

[@rplusgdj]

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

[@cRAYonhere]

In case, you have duplicates in your tree use root->data >= min && root->data

[@varunmanchanda3972]

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; }

[@AyushKumar-xe7ps]

Nice technique bro

[@shahriarmim4696]

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; }

[@mohitnikumbh593]

We can also have in-order traversal and check whether the current data is greater than or equal to previous data.

[@thesuperiorman8342]

The range for the second solution @15:00 should be: root->data > minValue && root->data

[@shreyanshabhiraj9734]

minValue is for right bst & maxValue is for left, so min of right>root->data & max of left data. so given is correct.

[@bolu3307]

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

[@priyanshujindal1995]

Instead of making IsBstUtil you can also use default paramters

[@madanmohan5661]

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.

[@kashyapsoni624]

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...

[@ramum5424]

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.

[@deepankdixit7541]

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.

[@vigneshwarm]

Can you share how you solved your problem?

[@shagun3062]

I have the same issue..kindly share it here

[@okaybossiamonyoutubeakkskd]

#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

[@pythonsimplified8594]

You are doing a really noble work. Please keep it up.............! I would even recommend to make a series on algorithms.

[@dg6546]

Thank you for helping out my homework... I can do it in O(n^2) but not O(n). Very helpful video!

[@proomm986]

I think it should be 0(log n) instead

[@pragyanshusharma1616]

Holy f***K what a good recurssion logic!!!!!! IMPRESSIVE

[@cody7464]

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 = &num; return IsInOrder(node, var); }

[@ooolongteeea]

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?

[@pinhastoav6647]

thank you mr. india, helped me alot.

[@arfatbagwan48]

Time complexity of first program is O(V^2+E^2)

[@marcushines4172]

...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.

[@yash21saraf]

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.

[@yash7432]

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

[@mmsky6316]

Thank you so much for these videos. Helping me tremendously.

[@anupampandey3758]

very nice! but space complexity and time complexity can be discussed in detail as well

[@snehalphatangare]

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)

[@frozentaco143]

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)

[@kanishkchandra5679]

why not inorder traversal?

[@random-0]

HE DID MENTION IT

[@zainabissa9748]

Perfect Explanation

[@sparshkanubhaikachhadiya5762]

Love how you pronounce "greater" in 1.75x speed😂. btw keep it up, love watching your videos.

[@navjyotsingh5386]

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

[@ImranAliyev]

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

[@Miguelonrm1]

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

[@vasantprabhu]

absolutely . even i had the same doubt. i wonder how come no one has addressed this

[@ntsingh577]

@@vasantprabhu this isn't a BST 6>5

[@MohitSharma-lz1nc]

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) ; }

[@nagarjunvinukonda162]

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?

[@staticFool]

very good explanation, sir why don't you explain avl,red black trees, graphs representations,graph traversals,heaps,hash tables and advanced data structures

[@AkshayCJ47]

Hey mycodeschool , at 14:22, in the second if condition, shouldn't it be root->data

[@cody7464]

@mycodeschool , this should be a small typo

[@idealspeaker1377]

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; }

[@madmaxx165]

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.

[@AnkitSingh-ni6sf]

Please make videos on dynamic programming also

[@8bit_hero850]

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;}

[@krishnanthiyagarajan]

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?

[@albert4392]

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?

[@duyvo4379]

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; }

[@vigneshwarm]

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); }

[@Flower_withanshi]

nice explanation and inorder technique is great!!

[@guddijain6818]

For duplicates just equal to( =) sign is enough while comparing with minvalue and max value???

[@markpascual100]

the C way of comparison

[@ayushthakur733]

Once you should traverse it for non-bst ....I think the code will fail ....put 5 in place of 1. @10:45 isBinarySearchTree function

[@user-zj9pq5xc7x]

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?

[@sasaskvorc594]

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); }

[@priyeshjaiswal5902]

Saša Škvorc doesn't worked

[@rahulmahawar9811]

awesomely explained..

[@yashsanthalia9561]

Sir u are amazing It is really helpful

[@shitijarora5712]

Sir how the time complexity of first method is n^2?

[@mehershrishtinigam5449]

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; }

[@swathik3491]

sir, please can you make lectures on graph algorithms

[@surabhi4332]

Swathi K they are already there....

[@ayushkoul5065]

Nice explaination!!!

[@SonnyCrisini]

Thank you. very clear lesson and great for refresher!

[@kunalgoyal9453]

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.

[@ISHANSDungeon]

Nice explanation sir. please upload algorithms of heapUp and heapDown, build heap and implementation also. thank you.

[@project_x0]

Great Video sir.

[@ankurgupta4696]

wow bro you teach so well :) :) :)

[@sarunuk]

Thanks for the awesome video :) @14:45 root->data should be > minValue ????

[@suman6327]

and root->data should be < maxValue :P Small mistake, please forgive him :D

[@pulkitgarg334]

+mycodeschool Can we not give default arguements instead of writing one more function?

[@shuyanli7366]

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

[@Deepakyadav-jr3gk]

use value less than INT_MAX and greater than INT_MIN.

[@werewolf_13]

I couldn't understand why a different function was required to call the original function in the second solution.

[@successally]

thank you so much for this amazing explaination.

[@alpishjain1317]

last approach is failing if the value of nodes are themselves INT_MIN && INT_MAX...

[@aniruddhapaturkar1884]

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?

[@usama57926]

very interesting algorithms

[@konstantinbeluchenko7418]

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; }

[@priyeshjaiswal5902]

Konstantin Beluchenko Best soln

[@sergeianonymoff1890]

Konstantin Beluchenko does this catch case B at 1:12?

[@NitishSarin]

+Sergei Anonymoff You are absolutely correct, It doesn't catch that case!

[@rishantjain7995]

How to handle cases of duplicates while checking with in order traversal?

[@aaronarellano497]

This dude is saving me!

[@shubhammalik5875]

Thanks for this video, really helped.

[@ketandshinde255]

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); }

[@baurks]

But this only works when the duplicates are not allowed. Isn't it? Please clarify.

[@167shivamrai2]

Super understanding...

[@mpalanipsbb]

Good video! Thank you

[@11m0]

Thank you

[@AmanSharma-ht5zq]

What does he mean when he says NULL is just a macro for 0 ?

[@markpascual100]

NULL is used to check if the pointer to the left or right child is empty i hope this cleared your doubts

[@vishymnit]

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.

[@MrSikiBu]

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.

[@mycodeschool]

-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

[@muhammadferoz8638]

@@mycodeschool Thanks A lot...……. May you be happy Always.....

[@nitinadarsh]

why we need to make another function when we already had BSTutil() method?

[@farid_45_bd]

For recursion is this code work properly? I tried many times but it wasn't working. Anybody has a solution using recursion?

[@vasantprabhu]

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?

[@vasantprabhu]

only the longer solution number 1 is accurate , where each node is compared with every other node in its subtree

[@vishalmishra1937]

sir plz make video on copy of bst without recursion

[@lijile2802]

well explained, thanks

[@SARCASMOOO]

You are a legend...

[@himanshu6489]

*was

[@keynesp]

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];

[@ronyra]

can someone write the code please

[@Andrey-ny2dv]

What is the complexity of first approach?

[@mehershrishtinigam5449]

INT_MAX and INT_MIN should be reversed while function call in IBST right ? It is wrong in the video?