CheckBinaryTreeIsValidBST.java

package com.thealgorithms.datastructures.trees;

/**
 * This code recursively validates whether given Binary Search Tree (BST) is balanced or not.
 * Trees with only distinct values are supported.
 * Key points:
 * 1. According to the definition of a BST, each node in a tree must be in range [min, max],
 *    where 'min' and 'max' values represent the child nodes (left, right).
 * 2. The smallest possible node value is Integer.MIN_VALUE, the biggest - Integer.MAX_VALUE.
 */
public final class CheckBinaryTreeIsValidBST {
    private CheckBinaryTreeIsValidBST() {
    }
    public static boolean isBST(BinaryTree.Node root) {
        return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private static boolean isBSTUtil(BinaryTree.Node node, int min, int max) {
        // empty tree is a BST
        if (node == null) {
            return true;
        }

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

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