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