# LeetCode 272: Closest Binary Search Tree Value II ## Problem Restatement We are given: - The root of a binary search tree - A floating-point `target` - An integer `k` We need to return the `k` values in the BST that are closest to `target`. The answer may be returned in any order. The problem guarantees that there is only one unique set of `k` closest values. Also, `k` is valid, so `k` does not exceed the number of nodes in the tree. ## Input and Output | Item | Meaning | |---|---| | Input | BST root, `target`, and `k` | | Output | `k` closest node values | | Tree rule | Inorder traversal gives values in sorted order | | Guarantee | One unique answer set | Example function shape: ```python def closestKValues(root: Optional[TreeNode], target: float, k: int) -> list[int]: ... ``` ## Examples Example 1: ```python root = [4, 2, 5, 1, 3] target = 3.714286 k = 2 ``` Tree: ```text 4 / \ 2 5 / \ 1 3 ``` The two closest values are: ```python [4, 3] ``` Example 2: ```python root = [1] target = 0.0 k = 1 ``` There is only one value. Answer: ```python [1] ``` ## First Thought: Traverse Everything and Sort A direct solution is: 1. Visit every node. 2. Store every value. 3. Sort values by distance from `target`. 4. Return the first `k` values. ```python class Solution: def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> list[int]: values = [] def dfs(node: Optional[TreeNode]) -> None: if node is None: return values.append(node.val) dfs(node.left) dfs(node.right) dfs(root) values.sort(key=lambda x: abs(x - target)) return values[:k] ``` This works for any binary tree, but it ignores the BST property. ## Problem With Sorting All Values If the tree has `n` nodes, sorting all values costs: ```python O(n log n) ``` The BST gives us sorted order through inorder traversal. Once values are sorted, the `k` closest values form a contiguous window around the target. We can maintain that window directly. ## Key Insight Inorder traversal of a BST visits values in increasing order. For example, this tree: ```text 4 / \ 2 5 / \ 1 3 ``` has inorder values: ```python [1, 2, 3, 4, 5] ``` We maintain a deque of at most `k` values. As we scan sorted values from left to right: - If the deque has fewer than `k` values, append the current value. - Otherwise compare: - The oldest value at the left side of the deque - The new current value If the current value is closer to the target, remove the leftmost value and append the current value. If the current value is farther, then all later values will be even larger. Since traversal is sorted, we can stop early. ## Algorithm 1. Create an empty deque. 2. Do inorder traversal. 3. For each visited value: - If the deque size is less than `k`, append it. - Else compare the current value with the deque's leftmost value. - If current value is closer: - Pop from the left. - Append current value. - Otherwise: - Stop traversal early. 4. Return the deque as a list. ## Walkthrough Use: ```python values = [1, 2, 3, 4, 5] target = 3.714286 k = 2 ``` Start: ```python deque = [] ``` Visit `1`. ```python deque = [1] ``` Visit `2`. ```python deque = [1, 2] ``` Visit `3`. Compare `3` with the leftmost value `1`. ```python abs(3 - 3.714286) < abs(1 - 3.714286) ``` So remove `1` and append `3`. ```python deque = [2, 3] ``` Visit `4`. Compare `4` with `2`. ```python abs(4 - 3.714286) < abs(2 - 3.714286) ``` So remove `2` and append `4`. ```python deque = [3, 4] ``` Visit `5`. Compare `5` with `3`. ```python abs(5 - 3.714286) > abs(3 - 3.714286) ``` Now `5` is farther than the oldest value in the window. Since later values will be even larger, stop. Answer: ```python [3, 4] ``` Returning `[4, 3]` is also accepted because any order is allowed. ## Correctness Inorder traversal visits BST values in sorted order. For sorted values, the `k` closest values to a target form a contiguous block. If a value on the left side is farther than a later value, replacing it moves the window closer to the target. The deque always stores the best size-`k` window among the values seen so far. When the deque has fewer than `k` values, every visited value must be kept. Once the deque has `k` values, the leftmost value is the farthest candidate on the low side of the current window. If the current value is closer than that leftmost value, replacing it improves the window. If the current value is not closer, then because values are increasing, every later value will be at least as large and therefore no closer than the current value on the right side. So traversal can stop safely. Thus the deque contains exactly the `k` closest values when the algorithm finishes. ## Complexity Let `n` be the number of nodes and `h` be the tree height. | Metric | Value | Why | |---|---|---| | Time | `O(n)` worst case | In the worst case we visit every node | | Space | `O(k + h)` | Deque stores `k` values, recursion uses height `h` | Early stopping may visit fewer than `n` nodes. ## Implementation ```python from collections import deque from typing import Optional, List # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]: window = deque() stopped = False def inorder(node: Optional[TreeNode]) -> None: nonlocal stopped if node is None or stopped: return inorder(node.left) if stopped: return if len(window) < k: window.append(node.val) else: left_diff = abs(window[0] - target) current_diff = abs(node.val - target) if current_diff < left_diff: window.popleft() window.append(node.val) else: stopped = True return inorder(node.right) inorder(root) return list(window) ``` ## Code Explanation The deque stores the current best window: ```python window = deque() ``` The flag `stopped` allows early termination: ```python stopped = False ``` Inorder traversal visits values from smallest to largest: ```python inorder(node.left) ... inorder(node.right) ``` While the window is not full, we append values: ```python if len(window) < k: window.append(node.val) ``` Once it is full, compare the new value with the oldest value: ```python left_diff = abs(window[0] - target) current_diff = abs(node.val - target) ``` If the new value is closer, update the window: ```python window.popleft() window.append(node.val) ``` Otherwise, stop traversal: ```python stopped = True ``` Finally, convert the deque to a list. ## Testing ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def normalize(xs: list[int]) -> list[int]: return sorted(xs) def run_tests(): s = Solution() root = TreeNode( 4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(5), ) assert normalize(s.closestKValues(root, 3.714286, 2)) == [3, 4] assert normalize(s.closestKValues(root, 3.0, 1)) == [3] assert normalize(s.closestKValues(root, 0.0, 2)) == [1, 2] assert normalize(s.closestKValues(root, 10.0, 2)) == [4, 5] assert normalize(s.closestKValues(root, 3.5, 3)) == [2, 3, 4] root = TreeNode(1) assert s.closestKValues(root, 0.0, 1) == [1] print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | Standard example | Closest values around target | | `k = 1` | Reduces to closest single value | | Target below all nodes | Returns smallest values | | Target above all nodes | Returns largest values | | Larger `k` | Keeps a window of several values | | Single node | Smallest valid tree |