Check if a binary tree is a binary search tree using a static method

Question

I have to create a static method that checks if a given tree is a binary search tree. It takes a BinaryTree<String> as its argument and it can only touch each node once.

I previously had my trees populated with numbers, but the datatype as String, I have now switched them to letters, since some have thought that I want to use Integers.

The problem I am experiencing is that the boolean bst isn't being tripped when my isBST() method is performed on tree4.

What I have so far is this:

public class BinarySearchTree < T extends Comparable < ? super T >> {
    public static boolean isBST(BinaryTree<String> tree) {
        boolean bst = true;

        if (tree.getRootData() != null) {
            Iterator<String> iterator = tree.getInorderIterator();
            String prev = iterator.next();

            while (bst && iterator.hasNext()) {
                String next = iterator.next();
                System.out.println(next); // Debug purposes only
                if (prev.compareTo(next) > 0) {
                    bst = false;
                }
            }
        }
        return bst;
    }
}

For my test cases, I have this:

public class Test {
    public static void main(String[] args) {
        BinarySearchTree<String> tree1 = new BinarySearchTree<String>();
        BinarySearchTree<String> tree2 = new BinarySearchTree<String>();

        BinaryTree<String> h           = new BinaryTree<String>("h");
        BinaryTree<String> g           = new BinaryTree<String>("g");
        BinaryTree<String> f           = new BinaryTree<String>("f");
        BinaryTree<String> e           = new BinaryTree<String>("e", f, g);
        BinaryTree<String> d           = new BinaryTree<String>("d");

        BinaryTree<String> a           = new BinaryTree<String>("a");
        BinaryTree<String> b           = new BinaryTree<String>("b");

        BinaryTree<String> tree3       = new BinaryTree<String>("c", a, e);
        BinaryTree<String> tree4       = new BinaryTree<String>("c", a, b);

        System.out.println("BinarySearchTree.isBST(tree3): " + BinarySearchTree.isBST(tree3));
        System.out.println("BinarySearchTree.isBST(tree4): " + BinarySearchTree.isBST(tree4));
    }
}

This returns the following output:

c
f
e
g
BinarySearchTree.isBST(tree3): true
c
b
BinarySearchTree.isBST(tree4): true

When I printed out the compareTo statement from within my static method, I saw that for the second tree (tree4) it returns -1 when it hits b. Which is why for tree4, it returns true because the boolean isn't tripped.

Any suggestions on this?

Answer 1

The compareTo() function of String works on the alphabetical order (natural order) of the String rather than the actual numeric value (that you want to compare).
Comparing String values of Integers, doesn't make much sense.

Anyway, in your example - you need to update 'prev', while executing, in your sample tree every inorder successor is being compared to 4 (as its never updated) and all the values are more than 4, so true is returned.

In the other case, (when you change 9 to 10) lexicographically, 10 < 4 so you are getting false. So, if you want to compare the 'real' value of integers, use Integer, rather than String.

Use BinaryTree<Integer>tree instead, and your solution should work