Is BST
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/***************************************************************************
 * Author: Isai Damier
 * Title: Is BST
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Indicate whether the given binary tree is a BST. isBST allows for
 *   either flavors of BST: left < node < right or right < node < left.
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n).
 *
 * Technical Details: This is an integrity ordeal algorithm (I hope this
 *   phrase catches on). First the input is allowed to make a claim; then
 *   the claim is severely tested for veracity. If any contradiction is
 *   found, the input fails. For instance, if an input claims to be a
 *   left < node < right BST, then it is sent to lnr for its trial.
 *
 * Note: This function has not been fully tested for true negatives.
 *    See attached unit test.
 *
 * RNL:
 *   Assume n.left.data > n.data > n.right.data. If a counter
 *   instance is found, return false. Otherwise return true.
 *
 * LNR:
 *   Assume n.left.data < n.data < n.right.data. If a counter
 *   instance is found, return false; otherwise return true.
 *
 * lnr and rnl are symmetrical to each other.
 **************************************************************************/
 public static boolean isBST(Node root) {
  if (null != root) {
    if (null != root.left && root.left.data < root.data) {
      return lnr(root);
    }
    if (null != root.right && root.right.data < root.data) {
      return rnl(root);
    }
  }
  return true;
}
 
private static boolean rnl(Node n) {
  if (null == n) {
    return true;
  }
  if (null != n.left && n.left.data < n.data) {
    return false;
  }
  if (null != n.right && n.right.data > n.data) {
    return false;
  }
  return rnl(n.left) && rnl(n.right);
}
 
private static boolean lnr(Node n) {
  if (null == n) {
    return true;
  }
  if (null != n.left && n.left.data > n.data) {
    return false;
  }
  if (null != n.right && n.right.data < n.data) {
    return false;
  }
  return lnr(n.left) && lnr(n.right);
}