Check if a binary tree is binary search tree or not

See complete series on data structures here:

In this lesson, we have written a program in C/C++ to verify whether a given binary tree is binary search tree or not.

[manakupadhyay]

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

[sumitsaini]

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.

[mrmca]

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.

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

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

[music-on]

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.

[manishkumar]

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

[ambershekhar]

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

[chayakumarsedutainment]

2:10 we have boolean type in C #include <stdbool.h>

[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

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

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

[varunmanchanda]

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

[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<=current, else return true. Much easier to implement, with less function calls.

[cRAYonhere]

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

[deepakjain]

Please upload videos on interview questions like dynamic programming

[mohitnikumbh]

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

[madanmohan]

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.

[ajaydattatray]

The best video on youtube for data structures