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

Example function shape:

def closestKValues(root: Optional[TreeNode], target: float, k: int) -> list[int]:
    ...

Examples

Example 1:

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

Tree:

    4
   / \
  2   5
 / \
1   3

The two closest values are:

[4, 3]

Example 2:

root = [1]
target = 0.0
k = 1

There is only one value.

Answer:

[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.

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:

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:

    4
   / \
  2   5
 / \
1   3

has inorder values:

[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:

values = [1, 2, 3, 4, 5]
target = 3.714286
k = 2

Start:

deque = []

Visit 1.

deque = [1]

Visit 2.

deque = [1, 2]

Visit 3.

Compare 3 with the leftmost value 1.

abs(3 - 3.714286) < abs(1 - 3.714286)

So remove 1 and append 3.

deque = [2, 3]

Visit 4.

Compare 4 with 2.

abs(4 - 3.714286) < abs(2 - 3.714286)

So remove 2 and append 4.

deque = [3, 4]

Visit 5.

Compare 5 with 3.

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:

[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.

Early stopping may visit fewer than n nodes.

Implementation

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:

window = deque()

The flag stopped allows early termination:

stopped = False

Inorder traversal visits values from smallest to largest:

inorder(node.left)
...
inorder(node.right)

While the window is not full, we append values:

if len(window) < k:
    window.append(node.val)

Once it is full, compare the new value with the oldest value:

left_diff = abs(window[0] - target)
current_diff = abs(node.val - target)

If the new value is closer, update the window:

window.popleft()
window.append(node.val)

Otherwise, stop traversal:

stopped = True

Finally, convert the deque to a list.

Testing

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: