Java Program to check the given Binary Tree is Binary Search Tree(BST) or not ?

           In Previous Post, discussed about the height of the BST(Binary Search Tree)  In this post, we can discuss to write the java code to validate the given Binary Tree is a BST or not.

           In a Binary Tree, each node can have at most two nodes. For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right sub tree of the root node should be greater than the data of the root.

BSTValidation.java,

package com.practice;

class Node {
 
      int data;
      Node leftChild;
      Node rightChild;
 
      public Node(int data) {
           this.data = data;
           leftChild = null;
           rightChild = null;
      }
}

public class BSTValidation {
      Node root;
      public boolean isBinarySearchTree() {
   
            if(root == null) return Boolean.TRUE;
            return isBstValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
      }
 
      private boolean isBstValid(Node node, Integer minValue, Integer maxValue) {
 
            if(node == null) return Boolean.TRUE;
            if(node.data >= minValue && node.data < maxValue
                  && isBstValid(node.leftChild, minValue, node.data)
                  && isBstValid(node.rightChild, node.data, maxValue)) {
                    return Boolean.TRUE;
            } else {
                    return Boolean.FALSE;
            }
      }
    
      public static void main(String[] args) {
               

             BSTValidation tree = new BSTValidation();
        

             // first example, valid binary search tree
             tree.root = new Node(48);
             tree.root.leftChild = new Node(22);
             tree.root.rightChild = new Node(61);
             tree.root.leftChild.leftChild = new Node(12);
             tree.root.leftChild.rightChild = new Node(28);
             tree.root.rightChild.leftChild = new Node(54);
             tree.root.rightChild.rightChild = new Node(68);
             System.out.println(tree.isBinarySearchTree());
     
             // second example, not a valid bst
     
             tree.root = new Node(48);
             tree.root.leftChild = new Node(22);
             tree.root.rightChild = new Node(100);
             tree.root.leftChild.leftChild = new Node(12);
             tree.root.leftChild.rightChild = new Node(28);
             tree.root.rightChild.leftChild = new Node(54);
             tree.root.rightChild.rightChild = new Node(68);
             System.out.println(tree.isBinarySearchTree());
      }
}

Output : true
               false


Related Post:
1) Program to find the height of Binary Search Tree(BST) in Java
2) Program to find maximum and minimum value from Binary Search Tree in Java
3) Java Program to delete a node from Binary Search Tree(BST)
4) Java Program to Count the number of nodes and leaf nodes of Binary Tree
5) How to Remove duplicates from ArrayList in Java