1. Introduction

A Binary Search Tree (BST) is a binary tree in which for each node, the left child node has a value less than the node’s value, and the right child node has a value greater than the node’s value. One of the common problems in the realm of binary trees is determining if a given binary tree is a BST. In this post, we will explore how to solve this problem using Java.

2. Program Steps

1. Start with the root of the binary tree.

2. Check if the current node’s value is between a specified range (initially from Integer.MIN_VALUE to Integer.MAX_VALUE).

3. For each left child node, adjust the upper bound of the range. For each right child node, adjust the lower bound.

4. If any node does not adhere to its range, return false. Otherwise, if all nodes adhere to their ranges, return true.

3. Code Program

class Node {
    int value;
    Node left, right;

    public Node(int value) {
        this.value = value;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    boolean isBST() {
        return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    boolean isBSTUtil(Node node, int min, int max) {
        if (node == null) {
            return true;
        }

        if (node.value < min || node.value > max) {
            return false;
        }

        return (isBSTUtil(node.left, min, node.value - 1) && isBSTUtil(node.right, node.value + 1, max));
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(4);
        tree.root.left = new Node(2);
        tree.root.right = new Node(5);
        tree.root.left.left = new Node(1);
        tree.root.left.right = new Node(3);

        if (tree.isBST()) {
            System.out.println("This binary tree is a BST");
        } else {
            System.out.println("This binary tree is not a BST");
        }
    }
}

Output:

This binary tree is a BST

4. Step By Step Explanation

1. The Node class defines the structure of the binary tree, containing a value and two child nodes, left and right.

2. The isBST function is a helper function that initializes the validation using the isBSTUtil function, starting from the root of the binary tree.

3. The isBSTUtil function recursively checks each node in the binary tree. It ensures that the value of the current node lies between the specified min and max.

4. For the left child node, the maximum value is adjusted to the current node's value minus one. For the right child node, the minimum value is adjusted to the current node's value plus one.

5. If all nodes in the binary tree adhere to their respective ranges, it implies that the binary tree is a BST.