Check Tree is a BST or not Full Explanation

To check whether a binary tree is a Binary Search Tree (BST) or not. First we need to ensure that the properties of a BST are satisfied. A binary tree is a BST if for every node. The values in its left subtree are less than the node’s value. And the values in its right subtree are greater than the node’s value. Additionally, the left and right subtrees themselves must also be BSTs.

Here’s a Java implementation to check if a binary tree is a BST:

Explanation & Process

First, we define a TreeNode class to represent the nodes of the binary tree. Each node has an integer value (val) and two pointers (left and right) to its left and right children.
We create a class named BSTChecker, which contains the method isBST and its helper method isBSTHelper. The isBST method is the main entry point for checking if the binary tree is a BST.
The isBST method takes in the root of the binary tree as input and calls the helper method isBSTHelper, passing the root and the minimum and maximum possible values for a node’s value (which are set to Integer.MIN_VALUE and Integer.MAX_VALUE, respectively).
The helper method isBSTHelper is a recursive function that checks each node and its subtrees to ensure they satisfy the BST property.
If the node passed to isBSTHelper is null, it means we have reached an empty subtree (or leaf), which is considered a BST. So, the function returns true.
If the node is not null, we need to check if its value falls within the valid range defined by min and max. If the node’s value is less than or equal to the min value or greater than or equal to the max value, it violates the BST property, and the function returns false, indicating that it is not a BST.
If the node’s value is within the valid range, we recursively call isBSTHelper for the left and right subtrees, updating the min and max values accordingly. For the left subtree, the maximum value allowed becomes the current node’s value (since all values in the left subtree must be less than the current node’s value). For the right subtree, the minimum value allowed becomes the current node’s value. Or since all values in the right subtree must be greater than the current node’s value.
The function continues this recursive process until it reaches the leaves of the binary tree, checking each node along the way. If all nodes and their subtrees satisfy the BST property, the function will return true, indicating that the binary tree is a BST.
In the main method, we create two example binary trees: one that is a valid BST and another that is not a BST.
We call the isBST method for both trees and print the results. The output correctly identifies whether each tree is a BST or not based on the definition and properties of a BST.

Code:


// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BSTChecker {

    // Helper method to check if the binary tree is a BST
    public static boolean isBST(TreeNode root) {
        return isBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private static boolean isBSTHelper(TreeNode node, int min, int max) {
        if (node == null) {
            // Empty tree is considered a BST
            return true;
        }

        // Check if the current node's value is within the valid range
        if (node.val <= min || node.val >= max) {
            return false;
        }

        // Recursively check the left and right subtrees
        return isBSTHelper(node.left, min, node.val) && isBSTHelper(node.right, node.val, max);
    }

    public static void main(String[] args) {
        // Example of a BST
        TreeNode bstRoot = new TreeNode(4);
        bstRoot.left = new TreeNode(2);
        bstRoot.right = new TreeNode(5);
        bstRoot.left.left = new TreeNode(1);
        bstRoot.left.right = new TreeNode(3);

        boolean isBst = isBST(bstRoot);
        System.out.println("Is the binary tree a BST? " + isBst); // Output: Is the binary tree a BST? true

        // Example of a non-BST
        TreeNode nonBstRoot = new TreeNode(4);
        nonBstRoot.left = new TreeNode(2);
        nonBstRoot.right = new TreeNode(5);
        nonBstRoot.left.left = new TreeNode(6); // This violates the BST property

        boolean isNonBst = isBST(nonBstRoot);
        System.out.println("Is the binary tree a BST? " + isNonBst); // Output: Is the binary tree a BST? false
    }
}

Explanation

In the code above, we define a TreeNode class to represent the nodes of the binary tree. The isBST method is the main entry point for checking if the binary tree is a BST. It calls the private helper method isBSTHelper, which recursively checks each node and its subtrees to ensure they satisfy the BST property.

The helper method isBSTHelper takes in three parameters: the current node, the minimum valid value allowed for the node, and the maximum valid value allowed for the node. If the current node’s value falls outside this range, we know it’s not a BST, and the function returns false. Otherwise, it continues checking its left and right subtrees.

In the example, the first binary tree satisfies the BST properties. While the second one does not (the value 6 in the left subtree violates the BST property). Therefore, the output correctly identifies the trees as BST and non-BST, respectively.

Inorder Traversal in Binary Search Tree Full Explanation

Postorder Traversal in Binary Search Tree With Full Explanation

Preorder Traversal In Binary Search Tree Full Explanation

Binary Search Tree Traversal With Full Examples And Explanation

Difference Between Binary Tree and Binary Search Tree With Examples

Searching in Binary Search Tree | FlutterTPoint

Binary Search Tree With Full Examples FlutterTPoint

Factorial of a Number