# 15ms java solution with BST

• I defined a simple BST data structure, too complicate if writing a balanced BST. I didn't include parent node in TreeNode so the implementation is quite long, sorry about that.

``````private static class BSTree{
private static class TreeNode{
private TreeNode left = null, right = null;
private int id = 0;
public TreeNode(int i, TreeNode l, TreeNode r){
id = i;
left = l;
right = r;
}
}
private TreeNode root = null;
public BSTree(){}
TreeNode newest = new TreeNode(n, null, null);
if(root == null){
return -1;
}
TreeNode walk = root;
if(walk.id == n)    return 0;
int min = Integer.MAX_VALUE;
while(walk != null){
min = Math.min(Math.abs(walk.id - n), min);
if(walk.left == null && walk.id > n){
return min;
}
else if(walk.right == null && walk.id < n){
return min;
}
else if(walk.id > n)    walk = walk.left;
else if(walk.id < n)    walk = walk.right;
}
return -1;
}
public void remove(int n){
if(root.id == n){
root = recover(root);
return;
}
TreeNode walk = root;
while(walk != null){
if(walk.left != null && walk.left.id == n){
walk.left = recover(walk.left);
return;
}
else if(walk.right != null && walk.right.id == n){
walk.right = recover(walk.right);
return;
}
else if(walk.id > n)
walk = walk.left;
else if(walk.id < n)
walk = walk.right;
}
}
public TreeNode recover(TreeNode rt){
if(rt.left == null) return rt.right;
else if(rt.right == null)   return rt.left;
TreeNode walk = rt.right;
if(walk.left == null){
walk.left = rt.left;
return walk;
}
while(walk.left.left != null){
walk = walk.left;
}
TreeNode temp = walk.left;
walk.left = walk.left.right;
temp.left = rt.left;
temp.right = rt.right;
return temp;
}
}
``````

Then implemented the algorithm with maintaining a size k+1 BST, and searched each incoming element to get a minimum subtraction.

``````public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
BSTree tree = new BSTree();
for(int i = 0; i < nums.length; i++){
if(i > k)   tree.remove(nums[i-k-1]);
if(dist >= 0 && dist <= t)  return true;
}
return false;
}``````

``````class TreeNode(object):
def __init__(self):
self.val = None
self.left = None
self.right = None

class BSTree(object):
def __init__(self):
self.root = TreeNode()

def insert(self, n):
new_node = TreeNode()
new_node.val = n
if self.root.val == None:
self.root = new_node
return -1

node = self.root
min_val = float("inf")
while node != None:
if node.val == n:
return 0
min_val = min(min_val, abs(node.val - n))
if node.left is None and node.val > n:
node.left = new_node
return min_val
elif node.right is None and node.val < n:
node.right = new_node
return min_val
elif node.val > n:
node = node.left
elif node.val < n:
node = node.right
return -1

def delete(self, n):
if self.root.val == n:
self.root = self.rotate(self.root)
return
node = self.root
last_node = None
is_left = False
while node:
if node.val == n:
if is_left:
last_node.left = self.rotate(node)
else:
last_node.right = self.rotate(node)
return
last_node = node
if node.val > n:
node = node.left
is_left = True
elif node.val < n:
node = node.right
is_left = False

def rotate(self, del_node):
"""
return the root of the subtree after deleting del_node
"""
if del_node.left is None:
return del_node.right
elif del_node.right is None:
return del_node.left

node = del_node.right
if node.left is None:
node.left = del_node.left
return node
while node.left.left is not None:
node = node.left
tmp_node = node.left
node.left = node.left.right
tmp_node.left = del_node.left
tmp_node.right = del_node.right
return tmp_node

class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
if t < 0 or k < 1:
return False
nums_len = len(nums)
tree = BSTree()
for i in range(nums_len):
if i > k:
tree.delete(nums[i-k-1])
diff = tree.insert(nums[i])
if diff >= 0 and diff <= t:
return True
return False
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.