4
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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).

\$\endgroup\$
  • 1
    \$\begingroup\$ This sentence is ambiguous: Your new algorithm, however, will yield the same results as the old wrong way to find minValue and maxValue, so you got that right ... is the algorithm right, or wrong? To me it looks like Liondancer's changes are in fact broken, they are wrong, yet you seem to be saying they are working.... \$\endgroup\$ – rolfl Jan 17 '14 at 19:46
  • \$\begingroup\$ I've tried my code against a few BST and they seem to be giving me the right results but I'm not sure if I have considered everything \$\endgroup\$ – Liondancer Jan 17 '14 at 19:49
  • \$\begingroup\$ @rolfl I'm saying it's broken the same exact way that the old maxValue and minValue functions were broken. I'll edit. \$\endgroup\$ – snetch Jan 17 '14 at 20:27
  • \$\begingroup\$ @Liondancer Well, try it against my tree and tell us the results! \$\endgroup\$ – snetch Jan 17 '14 at 20:29
  • \$\begingroup\$ @snetch I tried my code against your tree and i got the wrong value. I built the tree wrong. However, I tried your tree with the method that uses minValue and maxValue and it seems to wrok \$\endgroup\$ – Liondancer Jan 17 '14 at 21:24

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.