## Thursday, May 16, 2019

### Problem Statement

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.
Example:
```Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

4
/ \
2   5
/ \
1   3

Output: [4,3]```
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Hints
• 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.
• Try to assume that each node has a parent pointer, it makes the problem much easier.
• Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
• You would need two stacks to track the path in finding predecessor and successor node separately.

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

At first glance, it might look very similar to the Closest Binary Search Tree Value. They need look similar except finding K in less than O(N) time is way harder, hehehehe Okay, more seriously.

#### Brute force, convert BST into sorted array

A quick thought would be if we traverse the BST in order, and put them into an array, now the problem becomes given an sorted array, find K elements that are closest to the target. That search should be done binary search find the target, and expand left and right compare the values with diff, take the smaller one and continue. Overall, this brute force idea time complexity would be O(N), and space complexity is O(N), N is the total number of tree nodes.

#### Use a max heap

Another way or anytime when you need to find K things, always think about heap. Here if we traverse the tree (in any order) and use a K sized max heap, we can solve the problem in O(NlgK) time complexity, O(K) space complexity

#### Use two stacks

This is a smart idea that I read from leetcode discussion. This is also following leetcode's hint. Keeping two separate stacks, one stack is all the nodes less or equal to the target (i.e., predecessor), the other is all the nodes larger than the target (i.e., successor). After that, merge those two stacks and keep the K closest element to target.

Note, the time complexity is still O(N + K). Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree.

You might also think about the double threaded tree given the hint, starting from the root, keep asking the predecessor and successor since double threaded tree allows you to have that. However, I didn't code this one up since it requires you to modify the tree structure which normally not allowed in interviews and also it's a bit too complicated for a coding interview

### Solutions

#### Brute force, convert BST into sorted array

Code it on your own :)
Time Complexity: assuming tree size is N, O(N)
Space Complexity: O(N)

#### Use a max heap

Time Complexity: assuming tree size is N, O(NlgK) because insertion into PQ is O(lgK)
Space Complexity: O(K)

#### Use two stacks

Time Complexity: assuming tree size is N, O(N+K) worst case. Think about the worst case all elements larger or smaller than targets. However, if the problem assumes the BST is balanced, then it would be come O(K + lgN) since ideally we only traverse half of the tree.
Space Complexity: O(N) worst case. Even if BST is balanced, we still need O(N/2), still O(N)

### References

#### 1 comment:

1. I think for the threaded tree idea, could find the node that value is closest to target, then use the predecessor or successor to find the k-1 values

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!