Closest Binary Search Tree Value Ii - Leetcode Solution

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:

1. Given target value is a floating point.
2. You may assume k is always valid, that is: k ≤ total nodes.
3. 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:

1. Traverse the BST using inorder traversal and store the values in an array.
2. Perform binary search on the array to find the index of the node that is closest to the target value.
3. Initialize two pointers left and right to the immediate left and right of the index of the closest value found.
4. 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.
5. 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.

1