Closest Binary Search Tree K-Values Problem — LeetCode Hard (Proposed Solution)
Background
In this and the upcoming posts, I will go deep in some CS problems with my proposed solutions. I will try to follow the simplest possible approach “that is acceptable and good enough but may not be the most optimal” to make it easy to absorb by everyone. Now, let’s start.
One of the interesting problems I checked recently is the closest binary search tree k-values problem.
Problem Statement
This is the original 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]
Proposal Solution (Iterative Approach + Priority Queue)
Like many other CS problems, we can have multiple acceptable solutions. But to show an easy to digest approach, we will try to solve it with a simple and good enough approach. The main idea of this approach is to traverse the input tree and push the first k values of this tree in a priority queue, and then use this priority queue’s values as a result. Let’s see a Java implementation for this.
Code
Complexity
Time complexity for the mentioned solution is O(K(Log(N)). Note that this problem can also be solved recursively which can reduce space complexity from O(N) to O(k + height of traversed tree).
Other possible solutions
We can use the quick select algorithm to solve this problem, it can have a better time complexity of O(N) but its worst-case scenario is O(N²).
What to do next
If you have a better solution, feel free to put in comments. Also, feel free to share this approach, and try it out in: https://leetcode.com/problems/closest-binary-search-tree-value-ii/
Level Up Coding
Thanks for being a part of our community! Subscribe to our YouTube channel or join the Skilled.dev coding interview course.
