Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

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

See, Difference Between Binary Tree and BST

Check out Binary Trees

Tree

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. 

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Previous article
Bottom View of a Binary Tree
Next article
Check for Children Sum Property in a Binary Tree
Live masterclass