A program to check if a binary tree is BST or not

Problem Statement

“A program to check if a binary tree is BST or not” states that you are given a binary tree and you need to check if the binary tree satisfies the properties of the binary search tree. So, the binary tree has the following properties: 

1. The left subtree should have nodes having a value less than the root
2. The right subtree should contain the nodes having data greater than root
3. The left and right subtree themselves should be a binary search tree that means they themselves should follow the properties of the binary search tree.

Example

Input

YES

Explanation: The given tree follows all the properties of a binary search tree. All the nodes in the left subtree are smaller than the root’s value. And the same goes for the right subtree, the nodes have a value greater than root. And the left subtree and right subtree themselves follow the properties of BST.

Input

NO

Explanation: The tree does not follow the property of BST, where all nodes in the left subtree should have a smaller value than root.

Approach for a program to check if a binary tree is BST or not

Naive Approach (Wrong Approach)

Here we simply write a program which checks if the left subtree’s root has value smaller than the root value. And the right subtree’s root has larger value than root. Then recursively check for left and right subtrees. But this approach is wrong because even though the left subtree root is smaller than root. There may be some node in the left subtree which has greater value as compared to the root. Similarly for the right subtree. So, in that case, this approach fails.

Run the algorithm on the given tree (image). You will find even though the algorithm will return that the given binary tree is BST. But since 1 in the right subtree is smaller than 2. So, we need to find some other approach.

Efficient Approach (Correct Approach)

We will use two variables minimum and maximum to define the range of our left and right subtrees. This will tell us if the elements in the left subtree lie in some range. This range will keep on changing as we keep on changing the subtrees. This method is just used to remove the flaw which we face in a naive approach. There we were not able to guarantee that all the elements in the left subtree will be smaller than root. And all the elements in the right subtree will be greater than root. Initially, we will call our BST checker with the minimum set as the minimum value of integer and maximum as integer’s maximum value. Because that is the range that should satisfy the root’s value. Now we will update the maximum for the left subtree as root’s value-1 and for the right subtree, we set the minimum value as root’s value. Now we will keep on setting the values of minimum and maximum appropriately and recursively calling the function for left and right subtree.

Code

C++ program to check if a binary tree is BST or not

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
} ;

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}

bool isThisBST(node* root, int minimum, int maximum)
{
    // if there is no tree
    if(!root)
        return true;

    // the root should be in the range defined by [minimum, maximum]
    if(root->data < minimum || root->data > maximum)
        return false;
    // if the root satisfies the value then we recursively check the same for left and right subtree
    // we set the minimum and maximum for left and right subtrees accordingly.
    return isThisBST(root->left, minimum, root->data-1) && isThisBST(root->right, root->data+1, maximum);
}

int main()
{
    node *root = create(2);
    root->left = create(1);
    root->right = create(4);
    root->right->left = create(3);
    root->right->right = create(5);

    bool isBST = isThisBST(root, INT_MIN, INT_MAX);
    cout<<((isBST == true) ? "YES" : "NO");
    return 0;
}

YES

Java program to check if a binary tree is BST or not

// Class that denote a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
} 

class Tree 
{ 
    static Node root; 
  
  // return true if the tree is BST else return false
    static boolean isThisBST(Node root, int minimum, int maximum)
    { 
        // if there is no tree
      if(root == null)
          return true;
  
      // the root should be in the range defined by [minimum, maximum]
      if(root.data < minimum || root.data > maximum)
          return false;
      // if the root satisfies the value then we recursively check the same for left and right subtree
      // we set the minimum and maximum for left and right subtrees accordingly.
      return isThisBST(root.left, minimum, root.data-1) && isThisBST(root.right, root.data+1, maximum);
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new Node(2); 
        tree.root.left = new Node(1); 
        tree.root.right = new Node(4); 
        tree.root.right.left = new Node(3); 
        tree.root.right.right = new Node(5); 
  
        boolean isBST = isThisBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    	System.out.print((isBST == true) ? "YES" : "NO");
    }
}

YES

Complexity Analysis

Time Complexity

O(N), because we only traversed through the tree. And a single traversal costs linear time complexity.

Space Complexity

O(1) constant space because we used only a constant number of variables but the program as a whole takes O(N) because there are N nodes in the tree.