Java Program to Check Whether a Binary Tree Is a Binary Search Tree (BST)

           In the previous post, we discussed the height of a Binary Search Tree (BST). In this post, we will learn how to write a Java program to validate whether a given binary tree is a Binary Search Tree (BST).

In a binary tree, each node can have at most two child nodes. For a binary tree to qualify as a Binary Search Tree (BST), the following conditions must be satisfied:

• All nodes in the left subtree of a node must have values less than or equal to the value of that node.

• All nodes in the right subtree of a node must have values greater than the value of that node.

If every node in the tree satisfies these conditions, then the binary tree is a valid Binary Search Tree (BST).

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