Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Optimal BST

Hard

0/120

Average time to solve is 55m

37 upvotes

Asked in companies

Problem statement

Given a sorted array of keys of BST and an array of frequency counts of each key in the same order as in the given inorder traversal. The frequency of an element is the number of searches made to that element. Construct a binary search tree from the given keys such that the total cost of all the searches is minimum.

Cost of searching a key is its frequency multiplied by its level number in the BST.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

For example:

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.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

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.

Output Format:

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.

Note

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.

Constraints:

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.

Sample Input 1:

Sample Output 1:

Explanation of sample input 1:

All the possible BST’s for the given input are shown in the above example.

Searching cost in first BST = 1 * 10 + 2 * 3 + 2 * 7 = 30. 
Searching cost in second BST = 1 * 7 + 2 * 3 + 3 * 10 = 43. 
Searching cost in third BST = 1 * 7 + 2 * 10 + 3 * 3 = 36.
Searching cost in fourth BST = 1 * 3 + 2 * 10 + 3 * 7 = 44. 
Searching cost in fifth BST = 1 * 3 + 2 * 7 + 3 * 10 = 47. 

Thus, 30 is the minimum cost of all the searches.

Sample Input 2:

Sample Output 2

Hint 1

Hint 2

Hint 3

Hint 4

Can you solve this using recursion?

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Recursion

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:

Create a helper function ‘optimalCostHelper’ to find the minimum cost to construct a bst.
Call this helper function by passing the keys, frequencies, starting and the ending index of the keys in consideration, and level/depth of the current root.

Algorithm for optimalCostHelper(keys, frequencies, startIdx, endIdx, curLevel):

If we have checked for all the nodes, return 0.
Initialise an integer variable ‘minimumCost’ by the maximum positive value.
Run a loop from startIdx to endIdx:
- Consider the current node as the root node.
- Recursively find the optimal cost of left and right subtree. The level of a child node is 1 + the level of the parent node i.e 1 + curLevel.
- Now, current’s node cost is the sum of product of its frequency and level, optimal cost for left subtree and optimal cost for right subtree.
- If this cost is less than the ‘minimumCost’, update ‘minimumCost’.
Return the minimum cost to construct the binary search tree.

Time Complexity

O(3 ^ N), where N is the number of keys.

We are considering every key as the root of the BST and then calculating the searching cost. In the worst case, we will be exploring all the possible BST’s that can be constructed from the given keys. With ‘N’ keys we can construct (2 * N) ! / (( N + 1 ) ! * (N!)) unique BST’s. This can be further generalized and the final time complexity will become O(3 ^ N).

Space Complexity

O(N), where N is the number of keys.

Recursion stack space of O(N) is used.

(75% EXP penalty)

(100% EXP penalty)

Optimal BST

Raj Ghosh

Interview problems

JAVA SOLUTION || Optimal BST ||

import java.util.* ;

import java.io.*;

import java.util.ArrayList;

public class Solution {

public static int optimalCost(ArrayList<Integer> keys, ArrayList<Integer> freq, int n) {

// Write your code here

int[][] dp = new int[n + 2][n + 2];

int[] pre = new int[n + 2];

for (int i = 1; i <= n; i++) {

pre[i] = pre[i - 1] + freq.get(i - 1);

}

pre[n + 1] = pre[n];

for (int i = 0; i < n; i++) {

for (int start = 1, end = 1 + i; start <= n - i; start++, end++) {

int ans = Integer.MAX_VALUE;

if (i == 0) {

dp[start][end] = freq.get(start - 1);

} else {

for (int j = start; j <= end; j++) {

ans = Math.min(ans, freq.get(j - 1) + dp[start][j - 1] - pre[start - 1] + pre[j - 1] + dp[j + 1][end] + pre[end] - pre[j]);

}

dp[start][end] = ans;

}

return dp[1][n];

}

3 views

0 replies

0 upvotes

Diptajit Saha

Interview problems

java solution

import java.util.* ;
import java.io.*; 
import java.util.ArrayList;

public class Solution {
	public static int optimalCost(ArrayList<Integer> keys, ArrayList<Integer> freq, int n) {
		// Write your code here
        int[][] dp = new int[n + 2][n + 2];
        int[] pre = new int[n + 2];

        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + freq.get(i - 1);
        }

        pre[n + 1] = pre[n];

        for (int i = 0; i < n; i++) {
            for (int start = 1, end = 1 + i; start <= n - i; start++, end++) {
                int ans = Integer.MAX_VALUE;

                if (i == 0) {
                    dp[start][end] = freq.get(start - 1);
                } else {
                    for (int j = start; j <= end; j++) {
                        ans = Math.min(ans, freq.get(j - 1) + dp[start][j - 1] - pre[start - 1] + pre[j - 1] + dp[j + 1][end] + pre[end] - pre[j]);
                    }
                    dp[start][end] = ans;
                }
            }
        }

        return dp[1][n];
	}
}

49 views

0 replies

1 upvote

Vivek chaurasia

Interview problems

java solution

import java.util.*;

public class Solution {

public static int optimalCost(ArrayList<Integer> keys, ArrayList<Integer> freq, int n) { // Write your code here ArrayList<ArrayList<Integer>> dp = new ArrayList<>(n + 2); for (int i = 0; i < n + 2; i++) { dp.add(new ArrayList<>(Collections.nCopies(n + 2, 0))); }

ArrayList<Integer> pre = new ArrayList<>(n + 2); pre.add(0);

for (int i = 1; i <= n; i++) { pre.add(pre.get(i - 1) + freq.get(i - 1)); }

pre.add(pre.get(n));

for (int i = 0; i < n; i++) { for (int start = 1, end = 1 + i; start <= n - i; start++, end++) { int ans = Integer.MAX_VALUE;

if (i == 0) { dp.get(start).set(end, freq.get(start - 1)); } else { for (int j = start; j <= end; j++) { ans = Math.min(ans, freq.get(j - 1) + dp.get(start).get(j - 1) - pre.get(start - 1) + pre.get(j - 1) + dp.get(j + 1).get(end) + pre.get(end) - pre.get(j)); }

dp.get(start).set(end, ans); } } }

return dp.get(1).get(n); } }

65 views

0 replies

1 upvote

Sarthak Rajpal

Interview problems

c++ solution

#include <bits/stdc++.h>

int optimalCost(vector<int>& keys, vector<int>& freq, int n)

{

// Write your code here

vector<vector<int>> dp(n+2,vector<int> (n+2,0));

vector<int> pre(n+2);

for(int i=1;i<=n;i++){

pre[i]=pre[i-1] + freq[i-1];

}

// pre[0]=pre[1];

pre[n+1] = pre[n];

for(int i=0;i<n;i++){

for(int start = 1,end=1+i;start<=n-i;start++,end++){

int ans=INT_MAX;

if(i==0){

dp[start][end] = freq[start-1];

} else{

for(int j=start;j<=end;j++){

// cout<<freq[j-1]<<" "<<dp[start][j-1]<<" "<<dp[j+1][end]<<endl;

ans = min(ans,freq[j-1] + dp[start][j-1] - pre[start-1] + pre[j-1] + dp[j+1][end] + pre[end] - pre[j]);

}

dp[start][end] = ans;

}

// cout<<dp[start][end]<<endl;

}

return dp[1][n];

}

272 views

0 replies

1 upvote

monish

Interview problems

python solution

def sum_freq(freq, i, j):
    res = 0
    for k in range(i, j + 1):
        res += freq[k]
    return res

def helper(keys, freq, l, r, dp):
    if l > r:
        return 0

    if dp[l][r] != -1:
        return dp[l][r]

    ans = float('inf')
    for i in range(l, r + 1):
        temp = sum_freq(freq, l, r) + helper(keys, freq, i + 1, r, dp) + helper(keys, freq, l, i - 1, dp)
        ans = min(ans, temp)

    dp[l][r] = ans
    return ans

def optimalCost(keys, freq, n):
    n = len(keys)
    dp = [[-1 for _ in range(n)] for _ in range(n)]
    return helper(keys, freq, 0, n - 1, dp)

python

136 views

0 replies

0 upvotes

sidd

c++ sol

#include <bits/stdc++.h>

int sum(vector<int>& freq,int i,int j)

{

int res=0;

for(int k=i;k<=j;k++)

{

res+=freq[k];

}

return res;

}

int helper(vector<int>& keys, vector<int>& freq,int l,int r,vector<vector<int>> &dp)

{

if(l>r){

return 0;

}

if(dp[l][r]!=-1){

return dp[l][r];

}

int ans=INT_MAX;

for(int i=l;i<=r;i++){

int temp=sum(freq,l,r)+helper(keys,freq,i+1,r,dp)+helper(keys,freq,l,i-1,dp); ans=min(ans,temp);

}

return dp[l][r]=ans;

}

int optimalCost(vector<int>& keys, vector<int>& freq, int n) {

int N=101;

vector<vector<int>> dp(N,vector<int>(N,-1));

return helper(keys,freq,0,n-1,dp);

}

beginners

484 views

0 replies

1 upvote

SP GAMING

Interview problems

C++ solution

#include <bits/stdc++.h>

int optimalCost(vector<int>& keys, vector<int>& freq, int n) { vector<vector<int>> dp(n,vector<int>(n,0)); for (int i = 0; i < n; i++) { dp[i][i]=freq[i]; } int diff=n-1; for (int i = 1; i <= diff; i++) { for (int row = 0; row <= n - 1; row++) { if (i + row <= n - 1) { int col = i + row; int extra = INT_MAX; for (int r = row; r <= col; r++) { int part1 = 0, part2 = 0; if (r - 1 >= row) { part1 = dp[row][r - 1]; } if (r + 1 <= col) { part2 = dp[r + 1][col]; } extra=min(extra, part1+ part2); dp[row][col] += dp[r][r]; } dp[row][col]+=extra; } } } return dp[0][n-1]; // Write your code here

}

405 views

0 replies

0 upvotes

Codestudio

Interview problems

Discussion thread on Interview Problem | Optimal BST

Hey everyone, creating this thread to discuss the interview problem - Optimal BST.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Optimal BST

407 views

4 replies

0 upvotes

Console