How to Determine If a Binary Tree Is a Valid BST in Java

Introduction

A binary search tree (BST) is a special kind of binary tree in which the value of each node is greater than or equal to the values in its left subtree and less than or equal to the values in its right subtree. This structure allows efficient searching, insertion, and deletion operations. In this article, we’ll explore how to check whether a given binary tree is a valid BST using Java.

Understanding BST Properties

To confirm that a binary tree is a valid binary search tree (BST), three key requirements must be met:

• All nodes located in the left subtree of any given node must have values strictly less than the value of that node.
• Similarly, every node in the right subtree must have a value that is strictly greater than that of the parent node.
• This ordering rule must apply not just to individual nodes, but consistently throughout the entire tree—meaning each subtree, whether left or right, must also satisfy the definition of a BST on its own.

Approach to Validate BST

A common and efficient approach involves recursion with a range of valid values for each node. We start with the full integer range and narrow it down as we traverse the tree. Each node’s value must fall within its allowed range.

Java Implementation

public class BinaryTreeBSTCheck {

    class Node {
        int key;
        Node leftNode, rightNode;

        Node(int key) {
            this.key = key;
        }
    }

    public boolean isBST(Node root) {
        return checkBST(root, null, null);
    }

    private boolean checkBST(Node current, Integer lowerLimit, Integer upperLimit) {
        if (current == null) {
            return true;
        }

        if ((lowerLimit != null && current.key <= lowerLimit) || 
            (upperLimit != null && current.key >= upperLimit)) {
            return false;
        }

        return checkBST(current.leftNode, lowerLimit, current.key) &&
               checkBST(current.rightNode, current.key, upperLimit);
    }

    public static void main(String[] args) {
        /*
                10
               /  \
              5    15
                  /  \
                 12   20
        */
        BinaryTreeBSTCheck checker = new BinaryTreeBSTCheck();
        Node root = checker.new Node(10);
        root.leftNode = checker.new Node(5);
        root.rightNode = checker.new Node(15);
        root.rightNode.leftNode = checker.new Node(12);
        root.rightNode.rightNode = checker.new Node(20);

        boolean isBSTree = checker.isBST(root);
        System.out.println("Tree is a valid BST: " + isBSTree);
    }
}

Example Explanation

In the example above, the tree structure follows BST rules:

• 5 is less than 10 and on the left
• 15 is greater than 10 and on the right
• 12 is less than 15 but greater than 10
• 20 is greater than 15

The isValidBST method verifies each node’s value is within the allowed range defined by its ancestors. The result will be true since this tree satisfies all the BST conditions.

Conclusion

Validating a binary tree as a BST can be effectively done using a recursive range-checking method. This ensures each node adheres to the BST property relative to its position in the tree. Using Java, the approach is both simple and efficient.

You can find the example code on Github.