Testing to see if tree is BST

Question

I found a function online that tests if a tree is a binary search tree:

private boolean isBST(Node node) { 
  if (node==null) return(true);

  // do the subtrees contain values that do not 
  // agree with the node? 
  if (node.left!=null && maxValue(node.left) > node.data) return(false); 
  if (node.right!=null && minValue(node.right) <= node.data) return(false);

  // check that the subtrees themselves are ok 
  return( isBST(node.left) && isBST(node.right) ); 
} 

I don't quite understand why maxValue and minValue are being used.

Here is the code for both functions:

private int minValue(Node node) { 
  Node current = node; 
  while (current.left != null) { 
    current = current.left; 
  }

  return(current.data); 
}

private int maxValue(Node node) { 
  Node current = node; 
  while (current.right != null) { 
    current = current.right; 
  }

  return(current.data); 
}

I made some edits to the isBST1 in my own way, but I'm not sure if there are any flaws in it or not.

static boolean isBST1(BinaryTreeNode root) {
    if (root == null) {
        return true;
    }
    if (root.left != null && root.left.value > root.value) {
        return false;
    }
    if (root.right != null && root.right.value < root.value) {
        return false;
    }
    return isBST1(root.left) && isBST1(root.right);

}

I am wondering if there is any sort of logic I am missing.

Answer 1

Your revised changes to the isBST(Node) method are broken. You only check that all Nodes have a data value that is left < me < right. In other words, you check to make sure that each individual node has appropriate left and right values.

As snetch points out though, the tree:

    5
   / \
  3   7
 / \   \
1   6   8

is a tree where the node with value 6 is broken. It should be to the right of the root node 5.

Using your logic, the left and right nodes for node 5 are good, and the left and right nodes for node 3 are good too. You will declare this tree to be 'good'.

When checking node 5 you should be comparing it on the left side to 6 and not to 3 in order to isolate the problem.

In other words, when checking a node, you need to check the maximum value of all its left-sided children against the minimum value of its right-side children.

While the sample code you have uses a recursive process to do that, you can also use a more complicated approach that does a depth-first traversal of the tree, and 'carries' the max (or mmin if you had to go down the right-side) value up from the bottom in order to test the state of the parent node. This method will reduce the scalability complexity from O(n log(n)) to O(n)

I have taken the liberty of writing a 'carry-up' version of the check which will visit fewer nodes to do the ckck, but will also do a bit more work at each stage to calculate a Min/Max value. The full system, using the same tree as snetch suggested, looks like:

private static class Node {
    private Node left, right;
    private final int value;
    public Node(int val) {
        this.value = val;
    }
    public Node(Node lt, int val, Node rt) {
        this.value = val;
        left = lt;
        right = rt;
    }
}

private static final class MinMax {
    private final int min, max;

    public MinMax(int min, int max) {
        super();
        this.min = min;
        this.max = max;
    }

}

private static final class NotBSTException extends IllegalStateException {
    private static final long serialVersionUID = 1L;
}

public static boolean isBST(Node n) {
    try {
        checkBST(n);
        return true;
    } catch (NotBSTException e) {
        return false;
    }
}

private static MinMax checkBST(final Node n) throws NotBSTException {
    if (n == null) {
        return null;
    }
    MinMax left = checkBST(n.left);
    MinMax right = checkBST(n.right);
    if (left != null && left.max > n.value) {
        throw new NotBSTException();
    }
    if (right != null && right.min < n.value) {
        throw new NotBSTException();
    }
    return new MinMax(left == null ? n.value : left.min, right == null ? n.value : right.max);
}

public static void main(String[] args) {
    Node tree = new Node(new Node(new Node(1), 3, new Node(6)), 5, new Node(null, 7, new Node(8)));
    System.out.println("3 ->" + isBST(tree.left));
    System.out.println("7 ->" + isBST(tree.right));
    System.out.println("5 ->" + isBST(tree));
}

And produces the output:

3 ->true
7 ->true
5 ->false

Answer 2

Here's a simple tree that can demonstrate a couple things:

    5
   / \
  3   7
 / \   \
1   6   8

minValue and maxValue are written so that the algorithm can catch the 6 that is out of place. And it seems like even the original versions of those functions are not doing that right. Your new algorithm will check the left value (3) and say it's okay, then check the 3-1-6 subtree and also say it's okay, when there's obviously a 6 that is on the left side and that is bigger than the root.

Your new algorithm, however, is broken in the same way as the old algorithm that uses minValue and maxValue is broken, so you translated code with functions into code with no functions "correctly" (didn't change anything).