Cost of searching a key is its frequency multiplied by its level number in the BST.
Input keys = [ 1, 3, 5 ] Frequency = [ 3, 10, 7 ] All the unique BST possible from the given keys are:
Among all these possible BST, the minimum cost is obtained from the below BST:
Cost = 1 * (freq of 3) + 2 * (freq of 1) + 2 * (freq of 5) = 30 where 1 is the level of node 3, 2 is the level of the node 1 and node 5.
The first line of input contains an integer T, the number of test cases. The first line of each test case contains an element ‘N’ denoting the number of elements in the BST. The second line of each test case contains ‘N’ space separated integers, sorted in ascending order. The third line of each test case contains ‘N’ space separated integers denoting the frequency of each element of the BST.
For every test case, print the minimum total cost of constructing the BST. The output of each test case is printed in a separate line.
1. Given BST will not contain duplicates. 2. You don’t have to print anything, it has already been taken care of. Just implement the function.
1 <= T <= 5 2 <= N <= 50 0 <= data <= 10^4 Where ‘T’ is the number of test cases, ‘N’ is the number of nodes in the given tree and ‘data’ denotes the value of the nodes in the given tree.
This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.
The idea is very simple. We will consider each key as the root and find an optimal solution by recursively finding the cost of left and right subtree. Then we will add the cost of the left and right subtree to the current’s node cost.
Cost of a node is the product of its frequency and its level.
Algorithm for optimalCostHelper(keys, frequencies, startIdx, endIdx, curLevel):