> For the complete documentation index, see [llms.txt](https://sisyphus.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sisyphus.gitbook.io/project/leetcode-notes/binary-search-tree/contain-duplicate-iii.md).

# Contain Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the **absolute** difference between **nums\[i]** and **nums\[j]**is at most t and the **absolute** difference between i and j is at most k.

**Example 1:**

```
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
```

**Example 2:**

```
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
```

**Example 3:**

```
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
```

Python's priority queue heapq is implemented via list, not like C++ or JAVA via Balanced BST. So heapq can not search range, like searching for the smallest node larger than target value (BST successor).

Below is a way to implement a not balanced BST to support that kind of requirement. **\[Not accepted yet]**

```python
class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if k <=0 or t < 0 or not nums:
            return False
        priorityQ = PriorityQ([])
        for i in range(len(nums)):
            candidate = priorityQ.successor(nums[i] - t)
            return nums[i] - t, candidate
            if candidate and candidate.val <= nums[i] + t:
                return True
            # if i >= k - 1:  # This is not k distance, this is k - 1 distance
            #     priorityQ.delete(nums[i - k + 1])
            if i >= k:
                priorityQ.delete(nums[i - k])
            priorityQ.insert(nums[i])
        
        return False
        
        
class TreeNode(object):
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val
        
class PriorityQ(object):
    def __init__(self, nums):
        if not nums:
            self.root = None
        else:
            self.root = TreeNode(nums[0])
        if len(nums) > 1:
            for i in range(1, len(nums)):
                self.insert(nums[i])
        
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(self.root, val)
        
    def successor(self, val):
        if not self.root:
            return None
        return self._successor(self.root, val, None)
        
    def delete(self, val):
        self._delete(self.root, val)
        
    def _insert(self, root, val):
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self._insert(root.left, val)
        else:
            root.right = self._insert(root.right, val)
        return root
    
    def _successor(self, root, val, successor):
        if not root:
            return successor
        if val < root.val:
            return self._successor(root.left, val, root)
        else:
            return self._successor(root.right, val, successor)
        
    def _delete(self, root, val):
        if not root:
            return None
        if val < root.val:
            root.left = self._delete(root.left, val)
            return root
        elif val > root.val:
            root.right = self._delete(root.right, val)
            return root
        else:
            if not root.left and not root.right:
                return None
            elif not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                successorInRightChild = self._successor(root, root.val, None)
                root.val = successorInRightChild.val
                root.right = self._delete(root.right, successorInRightChild.val)
                return root
        
```