Last Updated: 26 Mar, 2021
K Closest Values
Hard
Asked in companies
You have been given a Binary Search Tree of ‘N’ nodes, a real number ‘target’, and an integer ‘K’. Your task is to find exactly ‘K’ values from the given binary search tree that are closest(having the least absolute difference) to ‘target’.
A sample binary search tree
Note:
A Binary Search Tree is a binary tree data structure with the following properties:
The left subtree of any node contains nodes with a value less than the node’s value.
The right subtree of any node contains nodes with a value equal to or greater than the node’s value.
Right, and left subtrees are also binary search trees.
It is guaranteed that,
Values of all nodes in the given binary search tree are distinct positive integers.
There will be only one unique set of ‘K’ values in the binary search tree that is closest to the ‘target’.
Input Format:
The first line of the input contains an integer ‘T’ representing the number of test cases.
The first line of each test case contains a single real number, ‘target’ denoting the target value given in the problem.
The second line of each test case contains a single integer ‘K’, denoting the number of values that are to be selected from the binary search tree.
The third line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
For example, the input for the tree is depicted in the below image.
25
20 30
15 23 28 35
-1 -1 -1 -1 -1 -1 -1 -1
Explanation :
Level 1 :
The root node of the tree is 25
Level 2 :
Left child of 25 = 20
Right child of 25 = 30
Level 3 :
Left child of 20 = 15
Right child of 20 = 23
Left child of 30 = 28
Right child of 30 = 35
Level 4 :
Left child of 15 = null (-1)
Right child of 15 = null (-1)
Left child of 23 = null (-1)
Right child of 23 = null (-1)
Left child of 28 = null (-1)
Right child of 28 = null (-1)
Left child of 35 = null (-1)
Right child of 35 = null (-1)
The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
25 20 30 15 23 28 35 -1 -1 -1 -1 -1 -1 -1 -1
Output Format:
For each test case, print ‘K’ space-separated integer values from the given binary search tree that is closest to the ‘target’ in sorted order.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 100
1 <= data <= 10 ^ 9
0 <= K <= N
-10 ^ 9 <= target <= 10 ^ 9
Time Limit: 1 sec
Approaches
The idea here is to traverse the given binary search tree, and from all the available values in the tree, find the value which is closest (having least absolute difference) to ‘target’ and mark this value as taken. Repeat this process for ‘K’ times.
Algorithm:
- Declare an empty array say, ‘answer’ to store all the ‘K’ values that are closest to ‘target’.
- Run a loop for ‘K’ times:
- Declare a variable ‘minDifference’ to store the minimum absolute difference between ‘target’ and available values in the tree, and initialize it with 10 ^ 10
- Declare a variable ‘value’ to store the value from the tree having the least absolute difference from ‘target’.
- Call ‘findClosest’ function with ‘minDifference’, 'target', ‘value’, and root of the tree as arguments to update ‘value’.
- Insert ‘value’ in the array ‘answer’.
- Call the ‘mark’ function to mark the current ‘value’ in the tree as taken.
- Sort the array ‘answer’.
- Return ‘answer’.
Description of ‘findClosest’ function
This function is used to find a value from the available values in the binary search tree that is closest to the ‘target’
This function will take four parameters :
- root: A pointer to binary search tree node.
- target: A real number denoting the target value given in the problem.
- minDifference: A real number denoting the minimum absolute difference between ‘target’ and available values in the tree.
- value: An integer to store the closest value from the ‘target’
void findClosest(root, target, minDifference, value):
- If ‘root’ equals NULL, then return.
- If data of 'root' node is not marked, i.e., if data of 'root' node do not equal to -1
- If the absolute difference between data of 'root' node and ‘target’ is less than ‘minDifference’
- Update ‘minDifference’ i.e. do ‘minDifference’ = absolute difference of (root -> data - target).
- Store data of 'root' node in ‘value,’ i.e., value = data of ‘root.’
- If the absolute difference between data of 'root' node and ‘target’ is less than ‘minDifference’
- If the right child of ‘root’ is not NULL, then recur for ‘root -> right’.
- If the left child of ‘root’ is not NULL, then recur for ‘root -> left’.
Description of ‘mark’ function
This function is used to find a value from the given binary search tree that is the same as ‘value’ and mark it as taken.
This function will take two parameters :
- root: A pointer to binary search tree node.
- value: An integer denoting the value to be marked.
void mark(root, value):
- If ‘root’ equals NULL, then return.
- If data of 'root' node equal ‘value’
- Mark data of 'root' node as taken, i.e., do data of ‘root’ = -1
- If the right child of ‘root’ is not NULL, then recur for ‘root -> right’.
- If the left child of ‘root’ is not NULL, then recur for ‘root -> left’.
The idea here is to traverse the given binary search tree and insert all the values present in the tree into an array of integers. After inserting the values, we can sort the elements of this array in increasing order of absolute difference from ‘target’. After sorting, the first ‘K’ elements of this array will be the ‘K’ closest values from ‘target’.
Algorithm:
- Declare an empty array say, ‘arrValues’ to store all the values present in the given binary search tree.
- Call the ‘traverse’ function with ‘arrValues’ and root of BST as arguments.
- Sort ‘arrValues’ array in increasing order of absolute difference from ‘target’
- Declare an empty array say, ‘answer’ to store all the ‘K’ values that are closest to ‘target’.
- Run a loop for ‘i’ from 1 to ‘K’:
- Insert ‘arrValues[i]’ into ‘answer’
- Sort the array ‘answer’.
- Return ‘answer’
Description of ‘traverse’ function
This function is used to traverse the given binary search tree and insert all the values present in BST into ‘arrValues’
This function will take two parameters :
- root: A pointer to binary search tree node.
- arrValues: An array of integers to store all the values present in BST.
void traverse(root, arrValues):
- If ‘root’ equals NULL, then return.
- Insert data of 'root' node into ‘arrValues’.
- If the right child of ‘root’ is not NULL, then recur for ‘root -> right’.
- If the left child of ‘root’ is not NULL, then recur for ‘root -> left’.
The idea here is to traverse the given binary search tree and use a max - heap data structure to keep track of the ‘K’ closest values from ‘target’. We will traverse the given binary search tree, and for every value present in the tree, we will insert the absolute difference of the current value from ‘target’ into the max - heap. If the number of elements present in the max heap becomes greater than ‘K’, we will remove the element from the max - heap that has the maximum absolute difference from ‘target’.
Algorithm:
- Declare a max - heap data structure, say ‘maxHeap’, to store the ‘K’ closest values from the ‘target’ and their respective absolute differences from ‘target’.
- Call the ‘traverse’ function with ‘maxHeap’, ‘target’, ‘K’, and root of BST as arguments.
- Declare an empty array say, ‘answer’ to store all the ‘K’ values that are closest to ‘target’.
- Run a loop while ‘maxHeap’ is not empty:
- Insert the value of the top element of ‘maxHeap’ into ‘answer’
- Remove the top element from ‘maxHeap’
- Sort the array ‘answer’.
- Return ‘answer’
Description of ‘traverse’ function
This function is used to traverse the given binary search tree and store ‘K’ closest values from ‘target’ into ‘maxHeap’
This function will take four parameters :
- root: A pointer to binary search tree node.
- target: A real number denoting the target value given in the problem.
- maxHeap: A max - heap data structure to store the ‘K’ closest values from the ‘target’ and their respective absolute differences from ‘target’.
- k: An integer, given in the problem.
void traverse(root, target, maxHeap, k):
- If ‘root’ equals NULL, then return.
- Insert absolute difference of data of 'root' node from ‘target’ and data of 'root' node into the ‘maxHeap’.
- If the size of ‘maxHeap’ is greater than ‘K’
- Remove the top element from ‘maxHeap’
- If the right child of ‘root’ is not NULL, then recur for ‘root -> right’.
- If the left child of ‘root’ is not NULL, then recur for ‘root -> left’.
The idea here is to do an Inorder traversal of the given binary search tree. In inorder traversal of the binary search tree, we traverse all the values in increasing order. We will use a Double-ended queue to keep track of the ‘K’ closest values from ‘target’. We will traverse the given binary search tree, and for every value present in the tree, we will insert the absolute difference of the current value from ‘target’ into the double-ended queue. If the number of elements present in the double-ended queue becomes greater than ‘K’, we will compare the first and the last absolute difference values in the queue and remove the greater value from the queue.
Algorithm:
- Declare a double-ended queue, say ‘dQueue’, to store the ‘K’ closest values from the ‘target’ and their respective absolute differences from ‘target’.
- Call the ‘inorderTraversal’ function with ‘dQueue’, ‘target’, ‘K’, and root of BST as arguments.
- Declare an empty array say, ‘answer’ to store all the ‘K’ values that are closest to ‘target’.
- Run a loop while ‘dQueue’ is not empty:
- Insert the value of the front element of ‘dQueue’ into ‘answer’
- Remove the front element from ‘dQueue’
- Return ‘answer’
Description of ‘inorderTraversal’ function
This function is used to do an inorder traversal of the given binary search tree and store ‘K’ closest values from ‘target’ into ‘dQueue’
This function will take four parameters :
- root: A pointer to binary search tree node.
- target: A real number denoting the target value given in the problem.
- dQueue: A double-ended queue to store the ‘K’ closest values from the ‘target’ and their respective absolute differences from ‘target’.
- k: An integer, given in the problem.
void inorderTraversal(root, target, dQueue, k):
- If ‘root’ equals NULL, then return.
- If the left child of ‘root’ is not NULL, then recur for ‘root -> left’.
- Insert absolute difference of data of 'root' node from ‘target’ and data of 'root' node in the back of ‘dQueue’.
- If the size of ‘dQueue’ is greater than ‘K’
- If the absolute difference of the first element of ‘dQueue’ is greater than the absolute difference of the last element of ‘dQueue’
- Remove the first element of ‘dQueue’
- Else:
- Remove the last element of ‘dQueue’
- If the absolute difference of the first element of ‘dQueue’ is greater than the absolute difference of the last element of ‘dQueue’
- If the right child of ‘root’ is not NULL, then recur for ‘root -> right’.