Check whether a given tree is a Binary Search Tree in Java

In this Java tutorial, we will solve a well-known problem of Tree data structure. Given a tree, we will check whether the given tree is a Binary search tree or not.

Binary Search Tree in Java

A binary tree is a tree which has at most two children of a node. A binary search tree is a binary tree with some special properties:

• The node value must be greater than all the node values in the left subtree.
• The node value must be less than all the node values in the right subtree.
• Both left and right subtrees must also be a binary search tree.

Algorithm of Binary search tree

We will make a recursive function and we call this function for the root node.

For solving this problem we will use the following steps:

1. Call the function for the left node.
2. Call the function for the right node.
3. If the left subtree is not a BST then the tree is not a BST.
4. If the right subtree is not a BST then the tree is not a BST.
5. And, If node value is less then the max value of the left subtree then the tree is not a BST.
6. Also, If the node value is greater than the minimum value of the right subtree the tree is not a BST.
7. Else, the tree is a BST.

Program to check whether a given tree is Binary Search Tree in Java

public class BST {
    public static void main(String[] args) {
          /* Tree:
                      50
                     /  \
                    10   20
                  /  \   /  \
                30   60  70  80

         */
        TreeNode root = new TreeNode(50);
        root.left = new TreeNode(10);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(30);
        root.left.right = new TreeNode(60);
        root.right.left = new TreeNode(70);
        root.right.right = new TreeNode(80);

        System.out.println(isBST(root).isBst);

        /* Tree:
                      50
                     /  \
                    20   70
                  /  \   /  \
                10   30 60  80

         */
        TreeNode root2 = new TreeNode(50);
        root2.left = new TreeNode(20);
        root2.right = new TreeNode(70);
        root2.left.left = new TreeNode(10);
        root2.left.right = new TreeNode(30);
        root2.right.left = new TreeNode(60);
        root2.right.right = new TreeNode(80);

        System.out.println(isBST(root2).isBst);

    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
            left = null;
            right = null;
        }
    }

    static class BSTtriplet {
        boolean isBst;
        int max;
        int min;
    }

    static BSTtriplet isBST(TreeNode root) {
        if (root == null) {
            BSTtriplet br = new BSTtriplet();
            br.isBst = true;
            br.max = Integer.MIN_VALUE;
            br.min = Integer.MAX_VALUE;
            return br;
        }

        BSTtriplet lr = isBST(root.left);
        BSTtriplet rr = isBST(root.right);

        BSTtriplet myRes = new BSTtriplet();
        if (!lr.isBst || !rr.isBst || root.val < lr.max || root.val > rr.min) {
            myRes.isBst = false;
        } else {
            myRes.isBst = true;
        }

        myRes.min = Math.min(root.val, Math.min(lr.min, rr.min));
        myRes.max = Math.max(root.val, Math.max(lr.max, rr.max));
        return myRes;
    }
}

Output:

false
true

You can also read:

• Inorder, Preorder and Postorder traversals without Recursion in Java
• Program to find all permutations of a string in Java
• Pair with a given sum in an array using HashSet in Java