LeetCode Q272: Closest Binary Search Tree Value II (hard)

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: k ≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

1. Consider implement these two helper functions:
   1. getPredecessor(N), which returns the next smaller node to N.
   2. getSuccessor(N), which returns the next larger node to N.
2. Try to assume that each node has a parent pointer, it makes the problem much easier.
3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
4. You would need two stacks to track the path in finding predecessor and successor node separately.

Solution:

My solution is different from the hint provided. But it turns out that more than 90% people are using this solution.

In order traversal, use a window with size k to keep track the k closest number.

A O(log(n))+log(k) algorithm:
Following the hint, implement two function getPredecessor(N), getSuccessor(N).
Then, we search the BST. For each node, we run these two function. Compare their results with our target value, If both larger than target, we go left. If both smaller than target, we go right.

If one smaller and another larger. We use one stack to track and get K predecessors and K successors of current node. The process is very much like a reversed in-order traversal.