Test if a binary tree is an almost BST - EPI

Test if a binary tree is an almost BST

ReconstructAlmostBst.java
  public static boolean isRSDescendantAncestorOfM(
      BinaryTree<Integer> r, BinaryTree<Integer> s, BinaryTree<Integer> m) {
    BinaryTree<Integer> curR = r;
    BinaryTree<Integer> curS = s;

    // Interleaving searches from r and s.
    while (curR != null && curR != s && curS != null && curS != r) {
      if (curR == m || curS == m) {
        return true;
      }
      curR = curR.getData().compareTo(s.getData()) > 0 ? curR.getLeft() : curR
          .getRight();
      curS = curS.getData().compareTo(r.getData()) > 0 ? curS.getLeft() : curS
          .getRight();
    }

    // Reach the other before reaching m.
    if (curR == s || curS == r) {
      return false;
    }
    // Try to search m before reaching the other.
    return searchMBeforeT(curR, s, m) || searchMBeforeT(curS, r, m);
  }

  private static boolean searchMBeforeT(
      BinaryTree<Integer> p, BinaryTree<Integer> t, BinaryTree<Integer> m) {
    while (p != null && p != t && p != m) {
      p = p.getData().compareTo(t.getData()) > 0 ? p.getLeft() : p.getRight();
    }
    return p == m;
  }