# Create BinarySearchTree with ceiling() method, more efficient than TreeSet in library!

• If we use `TreeSet`, its `ceiling()` method will finally call the `getCeilingEntry()` method in `TreeMap` class.

But `getCeilingEntry()` method rollback to track the last element greater than the target value. That is not efficient enough.

`````````java
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) { // ROLLBACK FOR LAST ELEMENT GREATER THAN TARGET
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
``````

So if we spend a little while to write a new Binary Search Tree, that can optimize the performance. The following code runs 13ms, beats 97%.

``````public class Solution {
private static class TreeNode {
private long val;
private TreeNode left;
private TreeNode right;
private TreeNode(long n) { val = n; }
}
private static class BinarySearchTreeWithDummy {

private TreeNode dummy = new TreeNode(0); // sentinel

/** Insert new element into the tree
*  Return true if new value is added
*  Return false if this value is already exist
*/
TreeNode pre = dummy, cur = dummy.right; // head is always the right child of dummy
boolean fromLeft = false;
while (cur != null) {
long val = cur.val;
if (val > n) { // go left
pre = cur; cur = cur.left; fromLeft = true;
} else if (val < n) { // go right
pre = cur; cur = cur.right;
} else { // value already exist
return false;
}
}
TreeNode newNode = new TreeNode(n);
if (fromLeft) {
pre.left = newNode;
} else {
pre.right = newNode;
}
return true;
}
/**
* Return true if the target is removed
* Return false if target doesn't exist
*/
private boolean remove(long n) {
TreeNode pre = dummy, cur = dummy.right;
boolean fromLeft = false;
while (cur != null) {
if (cur.val > n) { // go left
pre = cur; cur = cur.left; fromLeft = true;
} else if (cur.val < n) { // go right
pre = cur; cur = cur.right;
} else { // find target
if (cur.left != null) {
cur = cur.left;
while (cur.right != null) { cur = cur.right; }
} else {
}
if (fromLeft) {
} else {
}
return true;
}
}
return false;
}
/**
* Return least element greater than the input n
* Return null if there is no element greater than n
*/
private Long ceiling(long n) {
TreeNode lastGreater = null;
TreeNode cur = dummy.right;
while (cur != null) {
if (cur.val > n) { // go left
lastGreater = cur; cur = cur.left; // use lastGreater to mark the last element greater than target , thus we don't need to rollback when we reach the leaf of the tree.
} else if (cur.val < n) {
cur = cur.right;
} else { // find target
return new Long(cur.val);
}
}
return (lastGreater == null)? null : new Long(lastGreater.val);
}
}
/**
* Solution based on Binary Search Tree
* Use my BinarySearchTreeWithDummy
*/
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length < 2) { return false; }
if (t < 0) { return false; }
BinarySearchTreeWithDummy tree = new BinarySearchTreeWithDummy();
for (int slow = 0, fast = 0; fast < nums.length; fast++) {
if (fast > k) { tree.remove((long)nums[slow++]); }
long floor = (long)nums[fast] - t;
long ceil = (long)nums[fast] + t;
Long firstGreaterThanFloor = tree.ceiling(floor);
if (firstGreaterThanFloor != null && firstGreaterThanFloor <= ceil) { return true; }