12
\$\begingroup\$

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 < max) &&
                     isBinarySearchTree(root.left, min, value)))
                {
                    return false;
                }
            }
            if (root.right != null) {
                Integer right = (Integer) root.right.value;
                if (!(value < right &&
                     (min == null || right > min) &&
                     (max == null || right < max) &&
                     isBinarySearchTree(root.right, value, max)))
                {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Builds a BinarySearchTree from an in-order array representation.
     * Assumes the tree is complete at each level.
     */
    public static BinarySearchTree fromArray(Integer[] repr) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.root = fromArray(repr, 0, repr.length - 1);
        return tree;
    }

    private static Node fromArray(Integer[] repr, int start, int end) {
        if (start > 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<Integer> toList(Node n) {
        ArrayList<Integer> 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[] args) {
    Integer[] arrayRepr = null;
    BinarySearchTree tree = null;

    arrayRepr = new Integer[] {};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(BinarySearchTree.isBinarySearchTree(tree));

    arrayRepr = new Integer[] {1,2,3,4,5,6,7};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(BinarySearchTree.isBinarySearchTree(tree));

    arrayRepr = new Integer[] {10,20,45,40,50,60,70};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(false == BinarySearchTree.isBinarySearchTree(tree));

    arrayRepr = new Integer[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(BinarySearchTree.isBinarySearchTree(tree));

    arrayRepr = new Integer[] {Integer.MIN_VALUE,42,Integer.MAX_VALUE};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(BinarySearchTree.isBinarySearchTree(tree));

    arrayRepr = new Integer[] {-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(BinarySearchTree.isBinarySearchTree(tree));

    arrayRepr = new Integer[] {-7,-6,-5,-4,-3,2,-1,0,1,2,3,4,5,6,7};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(false == BinarySearchTree.isBinarySearchTree(tree));

    arrayRepr = new Integer[] {-70,-60,-50,-40,-30,-35,-10,0,10,20,30,40,50,60,70};
    tree = BinarySearchTree.fromArray(arrayRepr);
    assert(false == BinarySearchTree.isBinarySearchTree(tree));
}
\$\endgroup\$
  • \$\begingroup\$ You should try using jUnit test cases instead of hacking together a series of tests in a main method :p \$\endgroup\$ – Dan Pantry Oct 25 '14 at 16:44
  • \$\begingroup\$ @DanPantry yep sorry, I needed to come up with a single executable class without external dependencies :) \$\endgroup\$ – Cristian Greco Oct 25 '14 at 16:46
  • \$\begingroup\$ For unit tests? That seems awfully strange, but I won't question your requirements \$\endgroup\$ – Dan Pantry Oct 25 '14 at 16:47
7
\$\begingroup\$

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 < max) &&
                 isBinarySearchTree(root.left, min, value)))
            {
                return false;
            }
        }
        if (root.right != null) {
            Integer right = (Integer) root.right.value;
            if (!(value < right &&
                 (min == null || right > 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);
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for your review! It seems that your code allows for repeated values. Also, I can't understand the comment "have a rule for null values... do they go at the left side?". The Integer cast instead is a mistake, I've been using generics before refactoring the code for simplicity :) \$\endgroup\$ – Cristian Greco Oct 25 '14 at 17:22
  • \$\begingroup\$ The rule-for-null is required if nodes can have null values. I am not sure how you had generics before, and still used the < and > comparisons. In general, on Code Review, you should present the code as it is, and not try to 'fix it up', or simplify it for here. These things make it worse, not better to review. \$\endgroup\$ – rolfl Oct 25 '14 at 17:25
5
\$\begingroup\$

I think you should not allow null values in a BST. The thing is, null values in general are not comparable, for example:

@Test(expected = NullPointerException.class)
public void testCannotCompareIntegerWithNull() {
    new Integer(3).compareTo(null);
}

The comparison above doesn't work, it will throw a NullPointerException.

Comparison is crucial in a BST. As such, I think you shouldn't allow elements that are not comparable, so shouldn't allow nulls.

Therefore, instead of passing null values here:

public static boolean isBinarySearchTree(BinarySearchTree tree) {
    return isBinarySearchTree(tree.root, null, null);
}

You should rewrite to use non-nulls:

public static boolean isBinarySearchTree(BinarySearchTree tree) {
    return isBinarySearchTree(tree.root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

And as a result, the implementation of the private isBinarySearchTree can become simpler too:

private static boolean isBinarySearchTree(Node node, Integer min, Integer max) {    
    if (node == null) {
        return true;
    } else if (min.compareTo(node.value) >= 0 || max.compareTo(node.value) <= 0) {
        return false;
    }

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

Note that when comparing min and max, you must use >= and <= instead of just > or <. Otherwise, trees like these could incorrectly pass the test:

 3      2
2 3    2 3
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.