Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Brute Force Approach
2.1.
C++ Solution
2.2.
JAVA Solution
2.3.
Python Solution
3.
Better Approach
3.1.
C++ Solution
3.2.
JAVA Solution
3.3.
Python Solution
4.
Efficient Approach
4.1.
C++ Solution
4.2.
JAVA Solution
4.3.
Python Solution
5.
5.1.
What is a Binary Tree?
5.2.
What is a Binary Search Tree?
5.3.
How to convert a Binary Tree to a Binary Search Tree?
6.
Conclusion
Last Updated: Mar 27, 2024

# Check if Binary Tree Is BST or Not

Harsh goyal
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Better Approach

The approach discussed above is inefficient in terms of time and space complexity for checking if a binary tree is BST or not, as we were iterating over the same node multiple times to get min and max values. A better approach is to pass the min and max information to every node while traversing the nodes. In this way, we can avoid traversing the same node again and again.

Step 1. Create a function that takes the root node, left min node, and right max node.

Step 2. Check if the current node’s value is within the limit or not. If not, then return false.

Step 3. Go to the left and right subtree by narrowing down the min and max node’s value allowed.

Step 4. Return true if left and right subtrees are also BST.

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

int isBST(struct Node* root, struct Node* left, struct Node* right)
{
//Base case, if root is NULL
if (root == NULL)
return 1;

//if left is not null then if left is greater than root return false
if (NULL != left && root->data <= left->data)
return 0;

//if right is not null then if right is smaller than root return false
if (NULL != right && root->data >= right->data)
return 0;

//check recursively for left and right subtrees
return isBST(root->left, left, root) &&
isBST(root->right, root, right);
}

//Driver function
int main(){

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, NULL,NULL))
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, TreeNode left, TreeNode right)
{
if(root == null)
{
return true;
}
if (null != left && root.val <= left.val)
{
return false;
}

if (null != right && root.val >= right.val)
{
return false;
}
return isBinarySearchTree(root.left, left, root) &&
isBinarySearchTree(root.right, root, 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,null,null))
{
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

def isBST(root, left, right):
#Base case, if root is NULL
if(root == None):
return 1

#if left is not null then if left is greater than root return false
if(None != left and root.data <= left.data):
return 0

#if right is not null then if right is smaller than root return false
if(None != right and root.data >= right.data):
return 0

#check recursively for left and right subtrees
return isBST(root.left, left, root) and isBST(root.right, root, right)

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, None, None)):
print("Binary Tree is BST")
else:
print("Binary Tree is not Bst")

return 0

#execute main
main()``````

Complexity Analysis of check binary tree BST  problem:

• Time Complexity: O(N). As we are traversing each node of the Binary Tree only in linear time, therefore, its time complexity is O(N), where 'N' is the total number of nodes.
• Space Complexity: O(1), Only Internal Stack space is being used for recursion.

## Efficient Approach

To understand the efficient approach to check if a binary tree is BST or not, we have to understand one property of binary search trees. If we do Inorder traversal of the binary search tree, then we get sorted data. We can use this property to solve this problem efficiently. By traversing the tree in the Inorder schema and checking that the previous node’s value is smaller than the current node's value, we can conclude the binary tree is BST. With this approach, our time complexity will be O(N) and will use O(1) space. Therefore it’s an efficient approach to check if the binary tree is BST or not.

Algorithm-

Step 1. Declare an instance-level variable previous and initialize it to null.

Step 2. Traverse the tree in an Inorder fashion.

Step 3. If the previous value is null, then set it to the current node.

Step 4. If the previous value is not null, then compare it with the current node.

Step 5. If the previous value is larger than the value of the current node, then returns false.

Step 6. Repeat Steps 3-5 for every node.

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

int isBST(struct Node* root)
{
static Node *previous = NULL;

//Base case, if root is NULL
if (root == NULL)
return 1;

// Checking returned value from left subtree
if (!isBST(root->left))
return 0;

if (previous != NULL && root->data <= previous->data )
return 0;

previous = root;

return isBST(root->right);
}

//Driver function
int main(){

//Building 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 {

TreeNode previous;

public boolean isBinarySearchTree(TreeNode root)
{
// Base case
if(root == null)
{
return true;
}

// Checking returned value from left subtree
if (!isBinarySearchTree(root.left))
{
return false;
}

if (previous != null && root.val <= previous.val )
{
return false;
}

previous = root;

return isBinarySearchTree(root.right);

}

public static void main(String[] args) {

// Building tree
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);

BST obj = new BST();

if (obj.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

previous = None

#Function to check if a given binary tree is BST or not
def isBST(root):
# using global variable previous to keep track of the previous node
global previous
previous = None
return isBST_inorder(root)

#Helper function that traverse the tree in inorder fashion
def isBST_inorder(root):

#previous is a global variable
global previous

# For empty tree return true
if root is None:
return True

if isBST_inorder(root.left) is False:
return False

# If the previous value is not null, then compare it with the current node.
# If the previous value is larger than the value of the current node, then returns false.
if previous is not None and previous.data > root.data:
return False

# Update previous
previous = root
return isBST_inorder(root.right)

#Driver function
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)

#check for BST
if(isBST(root)):
print("Binary Tree is BST")
else:
print("Binary Tree is not Bst")

return 0

#execute main
main()``````

Complexity Analysis of Check If Binary Tree Is BST Or Not problem:

• Time Complexity: O(N), we are doing inorder, preorder traversal, and traversing every single node in linear time, so its time complexity is O(N), where 'N' is the total number of nodes.
• Space Complexity: O(1), only Internal Stack space is being used for recursion.

Must Read Recursive Binary Search.

## Frequently Asked Questions

### What is a Binary Tree?

A Binary Tree is a Data Structure having a root node and at most two children nodes. Each of these children forms the left subtree and the right subtree. The end nodes or the leaf nodes have no children and are pointed by a null pointer.

### What is a Binary Search Tree?

A Binary Search Tree commonly known as BST is a binary tree in which the value of each node in the left subtree of a particular node is less than the value of that node, and the value of each node in the right subtree of that specific node is greater than the value of that node.

### How to convert a Binary Tree to a Binary Search Tree?

To convert a given binary tree to a binary search tree, we need to create an array that will store the Inorder traversal of the binary tree. We need to sort that array, do an Inorder traversal of a tree again and finally copy the elements to the tree nodes.

## Conclusion

In this article to check if a Binary tree is BST or not, we discussed what a Binary Search Tree is and discussed the different approaches to check if Binary tree is BST or not, along with its complexities. We learned about how we can leverage BST in order to traverse property to solve this problem efficiently. You can also refer to our DSA course in C++ and Java for more details on Trees and Binary Search Trees.