K Closest Values

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
AppleAmazon

Problem statement

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

1

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’.
Detailed explanation ( Input/output format, Notes, Images )
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.

1

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
Sample Input 1:
2
3.1
2
3 2 4 1 -1 -1 5 -1 -1 -1 -1
5.55
3
4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
3 4
5 6 7
Explanation For Sample Output 1:
For the first test case, the given binary search tree is shown below.

1 

Values of Nodes in the binary search tree = [ 1, 2, 3, 4, 5 ]

The absolute difference of each value with 3.1 is [ 2.1, 1.1, 0.1, 0.9, 1.9 ] respectively.

Therefore two nodes that are closest (having least absolute difference) to 3.1 are [3, 4]

For the second test case, the given binary search tree is shown below.

1

Values of Nodes in the binary search tree = [ 1, 2, 3, 4, 5, 6, 7 ]

The absolute difference of each value with 5.55 is [ 4.55, 3.55, 2.55, 1.55, 0.55, 0.45, 1.45 ] respectively.

Therefore three nodes that are closest (having least absolute difference) to 5.55 are [ 5, 6,  7 ]
Sample Input 2:
1
100
5
30 19 40 -1 25 35 55 -1 -1 -1 -1 -1 -1
Sample Output 2:
25 30 35 40 55
Hint

For every ‘i’ from 1 to ‘K’ inclusive, traverse the given binary search tree and find the i-th closest value from ‘target’.

Approaches (4)
Brute Force

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 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’.
Time Complexity

O(N * K), where ‘N’ is the total number of nodes in the given binary search tree, and ‘K’ is an integer given in the problem.

 

For every number from 1 to ‘K’ inclusive, we traverse all the ‘N’ nodes in the binary search tree. Moreover, it takes O(K * log(K)) time to sort the array  ‘answer’.

Therefore the total time complexity will be O(N * K) +  O(K * log(K)), which is the same as O(N * K).

Space Complexity

O(N + K), where ‘N’ is the total number of nodes in the given binary search tree.

 

In the worst case, when we have given a skew binary tree, we need O(N) extra space in the form of recursive calls. And it takes O(K) space to store all the ‘K’ values in the array ‘answer’.

Hence the overall space complexity will be O(N)  + O(K), which is O(N + K).

Code Solution
(100% EXP penalty)
K Closest Values
Full screen
Console