Check if a binary tree is binary search tree or not in java

ghz 10months ago ⋅ 123 views

To check if a binary tree is a binary search tree (BST) or not in Java, you can perform an inorder traversal of the tree and check if the elements are in sorted order. If the inorder traversal results in a sorted sequence, then the tree is a binary search tree. Here's a Java implementation of this approach:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class BSTChecker {
    TreeNode prev;

    public boolean isBST(TreeNode root) {
        prev = null;
        return isBSTUtil(root);
    }

    private boolean isBSTUtil(TreeNode node) {
        if (node == null) {
            return true;
        }

        // Check the left subtree
        if (!isBSTUtil(node.left)) {
            return false;
        }

        // Check current node
        if (prev != null && node.val <= prev.val) {
            return false;
        }
        prev = node;

        // Check the right subtree
        return isBSTUtil(node.right);
    }

    public static void main(String[] args) {
        // Example usage:
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);

        BSTChecker checker = new BSTChecker();
        boolean isBST = checker.isBST(root);
        System.out.println("Is the binary tree a binary search tree? " + isBST);
    }
}

This code defines a TreeNode class representing each node of the binary tree and a BSTChecker class with an isBST method to check if the given binary tree is a binary search tree. The isBSTUtil method performs an inorder traversal of the tree and checks if the elements are in sorted order. If any element violates the BST property, the method returns false, indicating that the tree is not a BST. Otherwise, it returns true.

#algorithm