Check if a Binary Tree is Valid BST or not

In this article, we will implement the algorithm to check if a given binary tree is a valid binary search(BST) tree or not. We will use a recursive approach in Java to implement the algorithm.

What is BST

Binary Search Tree(BST) is another variant of a binary tree which is mainly used for searching. Below are the properties of a valid binary tree.

• The left subtree of a node should contain only nodes with keys less than the nodes key.
• The right subtree of a node contains only nodes with keys greater than the nodes key.
• Both the left and right subtrees must be binary search trees.

Since, root data is always between left subtree data and right subtree data, performing inorder traversal on binary search tree produces a sorted list.

Binary Tree Node Implementation

Below is the binary tree node implementation in Java.

public class BinaryTreeNode {

    private int data;
    private BinaryTreeNode leftNode;
    private BinaryTreeNode rightNode;

//getters and setters

Java Program to Check Vallid BST

We will be using below BST as a reference to implement this algorithm. Here, we will recursively check if the left subtree key of a node is less than the nodes data and the right subtree of a node contains keys greater than the nodes key.

public class BSTCheck {

    public static void checkBST(BinaryTreeNode root){
        boolean isBst = checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        System.out.println("is BST : " + isBst);
    }

    private static boolean checkBST(BinaryTreeNode root, int minValue, int maxValue) {
        if (root == null){
            return true;
        }
        if (root.getData() > maxValue || root.getData() < minValue){
            return false;
        }
        return checkBST(root.getLeftNode(), minValue, root.getData())
                && checkBST(root.getRightNode(), root.getData(), maxValue);
    }

    public static void main(String[] args){
        BinaryTree tree = new BinaryTree();

        BinaryTreeNode root = new BinaryTreeNode(15);
        tree.root = root;
        root.setLeftNode(new BinaryTreeNode(7));
        root.getLeftNode().setLeftNode(new BinaryTreeNode(5));
        root.getLeftNode().setRightNode(new BinaryTreeNode(10));
        root.getLeftNode().getRightNode().setLeftNode(new BinaryTreeNode(8));

        root.setRightNode(new BinaryTreeNode(30));
        root.getRightNode().setLeftNode(new BinaryTreeNode(25));
        root.getRightNode().setRightNode(new BinaryTreeNode(35));
        BSTCheck.checkBST(root);
    }
}

Conclusion

In this article, we implemented the algorithm to check if a given binary tree is a valid BST or not in Java.