Introduction
This blog will discuss the various approaches to checking if a binary tree is BST or not. Before jumping into the problem, let’s first understand what exactly a Binary Search Tree is.
A Binary Search Tree is a type of tree data structure where for every node, all the nodes in the left subtree of this node have a value lesser than the current node’s value. Each and every node in the right subtree of this node have a value greater than the current node’s value, along with the fact that both the left subtree and right subtree are Binary Search Trees.
See, Difference Between Binary Tree and BST
Check out Binary Trees

Recommended: Try the Problem yourself before moving on to the solution.
Brute Force Approach
A straightforward approach to check if a binary tree is BST or not is to check at every node, the maximum value in the left subtree is less than the current node’s value, and the minimum value in the right subtree is greater than the current node’s value.
Step 1. Go to the left subtree and get the Maximum value from the left subtree.
Step 2. Check if the max value of the left subtree is more than the current node value, then return false.
Step 3. Check if the minimum value of the right subtree is less than the current node value, then return false.
Step 4. Recursively, follow steps 2 and 3 for the left and right subtree.
C++ Solution
#include<iostream>
#include<climits>
using namespace std;
// defining node of the tree
struct Node {
int data;
struct Node *left, *right;
};
//function to create a new node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
//function prototyping
int getMin(struct Node* node);
int getMax(Node* root);
int isBST(struct Node* node)
{
//Base case, if root is NULL
if (node == NULL)
return 1;
//Checking for the left subtree, if the max of left subtree is greater than root node return false
if (node->left != NULL && getMax(node->left) > node->data)
return 0;
//Checking for the right subtree, if the min of right subtree is less than root node return false
if (node->left != NULL && getMin(node->right) < node->data)
return 0;
//checking recursively for left and right subtrees
if (!isBST(node->left) || !isBST(node->right))
return 0;
//If None of the above condition satisfies then it is a BST
return 1;
}
// Function to get Min value of binary tree
int getMin(Node *root)
{
if(root==NULL)
return INT_MAX;
int res=root->data;
int left=getMin(root->left);
int right=getMin(root->right);
if(left<res)
{
res=left;
}
if(right<res)
{
res=right;
}
return res;
}
// Function to get Max value of binary tree
int getMax(Node* root)
{
// Base case
if (root == NULL)
return INT_MIN;
int res = root->data;
int lres = getMax(root->left);
int rres = getMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
//Driver function
int main(){
//Creating a binary tree
Node* root = newNode(10);
root->left = newNode(6);
root->right = newNode(4);
root->left->left = newNode(11);
root->left->right = newNode(2);
if(isBST(root))
cout<<"Binary Tree is BST";
else
cout<<"Binary Tree is not Bst";
return 0;
}
JAVA Solution
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val)
{
this.val = val;
}
}
public class BST {
public static boolean isBinarySearchTree(TreeNode root) {
if(root == null)
{
return true;
}
if(root.left != null && getMax(root.left) > root.val)
{
return false;
}
if(root.left != null && getMin(root.right) < root.val)
{
return false;
}
if(!isBinarySearchTree(root.left) || !isBinarySearchTree(root.right))
{
return false;
}
return true;
}
// Function to get Max value of binary tree
static int getMax(TreeNode root) {
if(root == null)
{
return Integer.MIN_VALUE;
}
int left = getMax(root.left);
int right = getMax(root.right);
return Math.max(root.val, Math.max(left, right));
}
// Function to get Min value of binary tree
static int getMin(TreeNode root) {
if(null == root)
{
return Integer.MAX_VALUE;
}
int left = getMin(root.left);
int right = getMin(root.right);
return Math.min(root.val, Math.min(left, right));
}
public static void main(String[] args) {
TreeNode root = new TreeNode(10);
root.left = new TreeNode(6);
root.right = new TreeNode(4);
root.left.left = new TreeNode(11);
root.left.right = new TreeNode(2);
if (isBinarySearchTree(root))
{
System.out.print("Binary Tree is BST");
}
else{
System.out.print("Binary Tree is not a BST");
}
}
}
Python Solution
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
#Function to get the maximum value of a binary tree
def getMax(root):
# Base case if tree is empty
if (root == None):
return float('-inf')
res = root.data
lres = getMax(root.left)
rres = getMax(root.right)
if (lres > res):
res = lres
if (rres > res):
res = rres
return res
#Function to get the minimum value of a binary tree
def getMin(root):
#Base case if tree is empty
if root is None:
return float('inf')
res = root.data
lres = getMin(root.left)
rres = getMin(root.right)
if lres < res:
res = lres
if rres < res:
res = rres
return res
def isBST(node):
#Base case, if root is NULL
if (node == None):
return 1
#Checking for the left subtree, if the max of left subtree is greater than root node return false
if (node.left != None and getMax(node.left) >= node.data):
return 0
#Checking for the right subtree, if the min of right subtree is less than root node return false
if (node.right != None and getMin(node.right) <= node.data):
return 0
#checking recursively for left and right subtrees
if (not isBST(node.left) or not isBST(node.right)):
return 0
#If None of the above condition satisfies then it is a BST
return 1
def main():
#Creating a binary tree
root = Node(10)
root.left = Node(6)
root.right = Node(4)
root.left.left = Node(11)
root.left.right = Node(2)
if(isBST(root)):
print("Binary Tree is BST")
else:
print("Binary Tree is not Bst")
return 0
#execute main
main()
Algorithm Complexity of the problem Check If Binary Tree Is BST Or Not:
- Time Complexity: The time complexity is O(N ^ 2), (where 'N' is the total number of nodes in the tree). We are processing each and every node twice to get maximum and minimum values of left and right subtrees.
-
Space Complexity: The Space Complexity is O(H ^ 2), (where 'H' is the height of the tree). As 2 stacks are being maintained internally, one for original tree traversal and one for getMax and getMin function which makes space complexity O(H * H) i.e. O(H ^ 2).
Check out this problem - Mirror A Binary Tree