LeetCode 272. Closest Binary Search Tree Value II

Problem Clarification

Implement a function closestKValues(root: TreeNode, target: float, k: int) -> List[int], which finds k values in a BST (binary search tree) that are closest to a target value.

assume k is always valid and k <= total nodes

the k values are not required to be ordered

Analysis

  1. Get sorted list from the BST (InOrder Traversal, time complexity $\Theta(N)$, space complexity $\Theta(N)$), then get the length-k slice:
    • a. Loop from the beginning of the list, update the closest k values list ans, stop when ans is full (length k) and abs(list_item - target) > abs(ans[0] - target), time complexity best $\Theta(k)$, worst $\Theta(N)$ -> total time comlexity $O(N)$
    • b. Truncate the sorted list from both ends, until it shrinks to length k, time complexity $O(N)$
    • c. Use Binary Search to find the closest value to target, then expand to two directions, stop when found k values. Time complexity $\Theta(logN + k)$, total time complexity $O(N)$
  2. No need to get the full sorted list beforehand, but rather get sorted element on the go, similar to 1a. Time complexity $O(N)$.
  3. (best time complexity) No need to acquire the sorted list to use binary search, but rather find the closest value in the raw BST, then expand to two directions predecessors and successors. Time complexity $O(logN + k)$ if BST is balanced, $O(N + k)$ if BST is totally unbalanced.

Code