How hard is LeetCode 272. Closest Binary Search Tree Value II?

LeetCode 272. Closest Binary Search Tree Value II is rated Hard on LeetCode.

What is the time complexity of LeetCode 272. Closest Binary Search Tree Value II?

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 272. Closest Binary Search Tree Value II?

The Python solution on this page uses O(1) auxiliary space.

Is LeetCode 272. Closest Binary Search Tree Value II a premium problem?

Yes. LeetCode 272. Closest Binary Search Tree Value II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Closest Binary Search Tree Value II — LeetCode 272 Python Solution

HardLeetCode PremiumStackTreeDepth-First SearchBinary Search TreeTwo PointersBinary TreeHeap (Priority Queue)

Problem: #272
Pattern: Heap / Priority Queue
Reading time: 4 min
Source: leetcode.com

The problem

Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.

Example

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

Python solution

Python

# 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: TreeNode, target: float, k: int) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            if len(q) < k:
                q.append(root.val)
            else:
                if abs(root.val - target) >= abs(q[0] - target):
                    return
                q.popleft()
                q.append(root.val)
            dfs(root.right)

        q = deque()
        dfs(root)
        return list(q)

Complexity

Measure	Complexity
Time	O(n) (after optional sort O(n log n))
Space	O(1) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 272. Closest Binary Search Tree Value II is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 272. Closest Binary Search Tree Value II?: LeetCode 272. Closest Binary Search Tree Value II is rated Hard on LeetCode.
What is the time complexity of LeetCode 272. Closest Binary Search Tree Value II?: The Python solution on this page runs in O(n) (after optional sort O(n log n)).
What is the space complexity of LeetCode 272. Closest Binary Search Tree Value II?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 272. Closest Binary Search Tree Value II cover?: LeetCode 272. Closest Binary Search Tree Value II is tagged Stack, Tree, Depth-First Search, Binary Search Tree, Two Pointers, Binary Tree and Heap (Priority Queue) on LeetCode.
Is LeetCode 272. Closest Binary Search Tree Value II a premium problem?: Yes. LeetCode 272. Closest Binary Search Tree Value II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.