Last Updated: 5 Dec, 2020
Sum Of K Smallest Elements In BST
Easy
Asked in companies
You are given a Binary search tree(BST) of integers and an integer ‘K’.
Your task is to find and return the sum of the first ‘K’ smallest elements of the BST.
Example:
For the given tree, ‘K = 3’.
The first ‘3’ smallest elements are 1, 3, and 4.
Sum of three smallest nodes in the BST = 1 + 3 + 4 = 8.
Thus, you should return ‘8’ as the answer.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of input contains the elements of the tree in the level order form separated by a single space.
If any node does not have a left or right child, take -1 in its place. Refer to the example below.
The second line of each test case contains a single integer ‘K’.
Example:
Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.
For example, the input for the tree (not a BST) depicted in the below image would be :
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = 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).
Output Format:
For each test case, return the integer denoting the sum of the first ‘K’ smallest elements in the given BST.
The output of each test case is printed in a separate line.
Note :
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^2
1 <= K <= 10^3
1 <= N <= 10^3
1 <= Node.data <= 10^9
Where 'N' denotes the number of nodes in the BST and 'Node.data' denotes the value of each node.
Time limit: 1 second
Approaches
The inorder traversal of the BST will give the sequence of nodes in the increasing order, which we will store in an array. We can then find the sum of the first ‘K’ elements of this array to get the final answer. The following function performs inorder traversal on the tree at ‘ROOT’ using recursion and stores the sequence in the array ‘INORDER’.
‘inorderTraversal(BinaryTreeNode ROOT, array INORDER)’:
- If ‘ROOT’ is equal to ‘NULL’, then ‘ROOT’ is not a valid node:
- Return.
- Call ‘inorderTraversal(ROOT->LEFT, INORDER)’. Traverse the left subtree of ‘ROOT’.
- ‘INORDER.append(ROOT->DATA)’. Append ‘ROOT’ to ‘INORDER’ as we visit it.
- Call ‘inorderTraversal(ROOT->RIGHT, INORDER)’. Traverse the right subtree of ‘ROOT’.
ALGORITHM:
- Create an empty array of integers ‘INORDER’.
- Call ‘inorderTraversal(ROOT, INORDER)’. Store the inorder traversal of the BST in the array ‘INORDER’.
- Set ‘SUM = 0’. Use it to compute the sum of the first ‘K’ smallest elements in the BST.
- Run a loop where ‘i’ ranges from ‘0’ to ‘min(K, INORDER.size())’:
- ‘SUM += INORDER[i]’.
- Return ‘SUM’ as the answer.
While performing the inorder traversal of the BST recursively, along with ‘ROOT’, pass the integer ‘K’ as a reference. Whenever we visit the ‘ROOT’ during the inorder traversal, reduce the value of ‘K’ by one and add ‘ROOT->DATA’ to the sum of nodes until now. If at any point during the recursion, ‘K’ becomes ‘0’, we have visited the first ‘K’ nodes, so stop the recursion. The function ‘inorderTraversal’ computes the sum of the first ‘K’ smallest nodes in the BST using inorder traversal.
‘integer inorderTraversal(BinaryTreeNode ROOT, integer K)’:
- If ‘ROOT’ is equal to ‘NULL’, then ‘ROOT’ is not a valid node:
- Return 0, as the sum.
- If ‘K’ is equal to ‘0’, then we have already visited the first ‘K’ nodes:
- Return 0, as the sum.
- Set ‘SUM = inorderTraversal(ROOT->LEFT, K)’. This is the sum of the nodes in the left subtree of ‘ROOT’.
- If ‘K’ is equal to ‘0’, then we have already visited the first ‘K’ nodes while traversing the left subtree of ‘ROOT’:
- Return ‘SUM’, as the sum.
- ‘SUM += ROOT->DATA’. Add the data at ‘ROOT’ to the sum until now.
- ‘K -= 1’. As we have visited the ‘ROOT’ node, decrease ‘K’ by one.
- ‘SUM += inorderTraversal(ROOT->RIGHT, K)’. Add the sum of the nodes in the right subtree of ‘ROOT’ to ‘SUM’.
- Return ‘SUM’, as the sum of the first ‘K’ smallest nodes of the BST at ‘ROOT’.
ALGORITHM:
- ‘SUM = inorderTraversal(ROOT, K)’. Compute the sum of the first ‘K’ smallest elements in the BST.
- Return ‘SUM’ as the answer.