[LeetCode 272] Closest Binary Search Tree Value II

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:
  2. i. getPredecessor(N), which returns the next smaller node to N.
  3. ii. getSuccessor(N), which returns the next larger node to N.
• 1. Try to assume that each node has a parent pointer, it makes the problem much easier.
• 1. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
• 1. You would need two stacks to track the path in finding predecessor and successor node separately.

Diffculty
Hard

Similar Problems
[LeetCode 270] Closest Binary Search Tree Value Easy

Analysis