Java code to determine the validity of a binary search tree

Write a code to determine the validity of a binary search tree (BST). A binary search tree is rooted binary tree, whose internal nodes each store a key and each have two distinguished sub-trees, commonly denoted left and right. The key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree. Below is an example of a BST:

Binary_search_tree

class Node {
public int value;
public Node left, right;

public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}

public class BinarySearchTree {
public static boolean isValidBST(Node root, int min, int max) {
if (root == null) {
return true;
}

if (max < root.value || root.value <= min) {
return false;
}

return isValidBST(root.left, min, root.value) && isValidBST(root.right, root.value, max );
}

public static boolean isValidBST(Node root) {
return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public static void main(String[] args) {
Node n1 = new Node(1, null, null);
Node n3 = new Node(3, null, null);
Node n2 = new Node(2, n1, n3);

System.out.println(isValidBST(n2));
}
}

Also to check if a binary search tree contains a value you can use the following method:

    public static boolean contains(Node root, int value) {
        boolean contains = false;

        if (root != null) {
            if (root.value == value) {
                contains = true;
            }
            else if (root.value < value) {
                contains = contains(root.right, value);
            }
            else if (root.value > value) {
                contains = contains(root.left, value);
            }
        }
        return contains;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *