My solution using BST. Remove elements may improve the efficiency

• Remove the elements that its distance from the current index is larger than k.
And then check if the BST contains value within [nums[i]-t,nums[i]+t]

``````class TreeNode
{
int value;
TreeNode left;
TreeNode right;
TreeNode parent;

public TreeNode(TreeNode parent,int value)
{
this.value=value;
this.parent=parent;
}
}

class BST
{
TreeNode root=null;
public BST()
{

}

public boolean insert(int x)
{
if(root==null)
{
root=new TreeNode(null,x);
}
else
{
TreeNode parent=root,cur=root;
while(cur!=null)
{
if(x==cur.value)
{
break;
}
else if(x<cur.value)
{
parent=cur;
cur=cur.left;
if(cur==null)
parent.left=new TreeNode(parent,x);
}
else
{
parent=cur;
cur=cur.right;
if(cur==null)
parent.right=new TreeNode(parent,x);
}
}

}
return true;
}

public TreeNode find(int x)
{
TreeNode cur=root;
while(cur!=null)
{
if(x==cur.value)
{
return cur;
}
else if(x<cur.value)
{
cur=cur.left;
}
else
{
cur=cur.right;
}
}
return cur;
}

public void remove(int x)
{
TreeNode node=find(x);
TreeNode y=null;
if(node.left==null||node.right==null)
y=node;
else
y=successor(node);
TreeNode child=null;
if(y.left!=null)
{
child=y.left;
}
else
{
child=y.right;
}
if(child!=null)
{
child.parent=y.parent;
}

if(y==root)
{
root=child;
}
else
{
if(y==y.parent.left)
{
y.parent.left=child;
}
else
{
y.parent.right=child;
}
}

if(y!=node)
{
node.value=y.value;
}

return ;

}

private TreeNode successor(TreeNode node) {

if(node.right!=null)
{
TreeNode cur=node.right;
while(cur.left!=null)
cur=cur.left;
return cur;
}
else
{
TreeNode p=node.parent;
while(p!=null&&node==p.right)
{
node=p;
p=p.parent;
}
return p;
}
}

public boolean containsInRange(int s,int e)
{
TreeNode cur=root;
while(cur!=null)
{

if(cur.value>=s&&cur.value<=e)
{
return true;
}
else if(cur.value>e)
{
cur=cur.left;
}
else
{
cur=cur.right;
}
}
return false;
}

}

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums==null||nums.length==0)
return false;
if(t<0)
return false;
BST bst=new BST();

for(int i=0;i<nums.length;i++)
{
if(i>k)
{
bst.remove(nums[i-k-1]);
}
int low=nums[i]>Integer.MIN_VALUE+t?nums[i]-t:Integer.MIN_VALUE;
int high=nums[i]<Integer.MAX_VALUE-t? nums[i]+t:Integer.MAX_VALUE;
if(bst.containsInRange(low,high))
{
return true;
}
else
{
bst.insert(nums[i]);
}
}

return false;
}``````

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