## Similar Problems

Similar Problems not available

# Closest Binary Search Tree Value Ii - Leetcode Solution

LeetCode: Closest Binary Search Tree Value Ii Leetcode Solution

Difficulty: Hard

Topics: binary-search-tree depth-first-search stack two-pointers tree binary-tree heap-priority-queue

Problem Statement:

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

- Given target value is a floating point.
- You may assume k is always valid, that is: k ≤ total nodes.
- You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]

Solution:

This problem can be solved using binary search and two pointers. We will first traverse the BST in inorder traversal and store the values in an array. By doing so, we get a sorted list of all the nodes in the BST. Now, we can perform binary search on this array to get the index of the node that is closest to the target value.

We will take two pointers, left and right initially pointing to the immediate left and right of the index of the closest value found. We will then keep moving the pointers towards the boundaries of the array, comparing the distance of the values pointed by both pointers to the target value. This will give us k values that are closest to the target value.

Here is the detailed step-by-step algorithm:

- Traverse the BST using inorder traversal and store the values in an array.
- Perform binary search on the array to find the index of the node that is closest to the target value.
- Initialize two pointers left and right to the immediate left and right of the index of the closest value found.
- While the number of elements added to the result list is less than k, do the following: a. If the distance of the value pointed by the left pointer is less than or equal to the distance of the value pointed by the right pointer, add the value pointed by the left pointer to the result list and move the left pointer to the left. b. Otherwise, add the value pointed by the right pointer to the result list and move the right pointer to the right.
- Return the result list.

Implementation:

Here is the Python code implementing the above algorithm:

class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]: # Step 1: Traverse the BST using inorder traversal and store the values in an array. nums = [] self.inorder(root, nums)

```
# Step 2: Perform binary search on the array to find the index of the node that is closest to the target value.
left, right = 0, len(nums) - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == target:
left, right = mid, mid
break
elif nums[mid] < target:
left = mid
else:
right = mid
# Check which side of the index has values closest to the target
if nums[right] <= target:
closest = right
elif nums[left] >= target:
closest = left
else:
closest = left if target - nums[left] < nums[right] - target else right
# Step 3: Initialize two pointers left and right to the immediate left and right of the index of the closest value found.
left, right = closest - 1, closest + 1
result = [nums[closest]]
# Step 4: While the number of elements added to the result list is less than k
while len(result) < k:
if left >= 0 and right < len(nums):
# Step 4a: If the distance of the value pointed by the left pointer is less than or equal to the distance of the value pointed by the right pointer
if abs(nums[left] - target) <= abs(nums[right] - target):
result.append(nums[left])
left -= 1
else:
result.append(nums[right])
right += 1
elif left >= 0:
result.append(nums[left])
left -= 1
else:
result.append(nums[right])
right += 1
# Step 5: Return the result list.
return result
def inorder(self, root: TreeNode, nums: List[int]):
if not root:
return
self.inorder(root.left, nums)
nums.append(root.val)
self.inorder(root.right, nums)
```

Time Complexity:

The time complexity of the algorithm is O(nlogn), where n is the number of nodes in the BST. The inorder traversal takes O(n) time and binary search takes O(logn) time. The while loop in step 4 can execute at most 2k times, taking O(k) time. Therefore, the overall time complexity is O(nlogn + k).

Space Complexity:

The space complexity of the algorithm is O(n), where n is the number of nodes in the BST. This is the space used to store the values of nodes in the array.

## Closest Binary Search Tree Value Ii Solution Code

`1`