Validating a Binary Search Tree

This is an implementation of a function to check the property of a Binary Search Tree, that is:


the key in any node is larger than the keys in all nodes in that
node's left subtree and smaller than the keys in all nodes in that
node's right sub-tree

I'm looking for reviews on code correctness and test cases.

public class BinarySearchTree {

    private Node root;

    private static class Node {

        private Integer value;
        private Node left;
        private Node right;

        Node(Integer value) {
            this.value = value;
        }
    }

    /**
     * Returns true if 'tree' is a binary search tree, false otherwise.
     */
    public static boolean isBinarySearchTree(BinarySearchTree tree) {
        return isBinarySearchTree(tree.root, null, null);
    }

    private static boolean isBinarySearchTree(Node root, Integer min, Integer max) {
        if (root != null) {
            Integer value = (Integer) root.value;
            if (root.left != null) {
                Integer left = (Integer) root.left.value;
                if (!(value > left &&
                     (min == null || left > min) &&
                     (max == null || left  min) &&
                     (max == null || right  end) {
            return null;
        }
        int m = start + ((end - start) / 2);
        Node n = new Node(repr[m]);
        n.left = fromArray(repr, start, m - 1);
        n.right = fromArray(repr, m + 1, end);
        return n;
    }

    /**
     * Returns an in-order array representation of the tree.
     */
    public Integer[] toArray() {
        return toList(root).toArray(new Integer[]{});
    }

    private List toList(Node n) {
        ArrayList values = new ArrayList<>();
        if (n != null) {
            values.addAll(0, toList(n.left));
            values.add(n.value);
            values.addAll(toList(n.right));
        }
        return values;
    }
}

Here some basic test code:

```
public static void main(String[] a

Looking in general, the code looks nice enough. I realize that you are using Integer as values because that's convenient, but I would prefer that you used generics, and a Comparator instance to work with, rather than relying on the autoboxing of Integer to int values.

So, taking your core method:

private static boolean isBinarySearchTree(Node root, Integer min, Integer max) {
    if (root != null) {
        Integer value = (Integer) root.value;
        if (root.left != null) {
            Integer left = (Integer) root.left.value;
            if (!(value > left &&
                 (min == null || left > min) &&
                 (max == null || left  min) &&
                 (max == null || right < max) &&
                 isBinarySearchTree(root.right, value, max)))
            {
                return false;
            }
        }
    }
    return true;
}

min and max should be comparables... ;-)

You should use compareTo() instead of doing the autoboxing/unboxing:

min == null || left > min

Finally, you have redundancies in your class that will be solved with a small restructuring...

• don't call it 'root', it's a recursive call, and it's not always the root...

• have a rule for null values... do they go at the left side?

• there's no need for the explicit cast of (Integer)root.value

Restructured, your recursion looks like....

private static boolean isBinarySearchTree(Node node, Integer min, Integer max) {

    if (node == null) {
        return true;
    }

    if (min != null && min.compareTo(node.value) > 0) {
        // node is not after (the same as) than min
        return false;
    }
    if (max != null && max.compareTo(node.value) <= 0) {
        return false;
    }

    return isBinarySearchTree(node.left, min, node.value)
        && isBinarySearchTree(node.right, node.value, max);
}

StackExchange Code Review Q#67928, answer score: 7