Optimal BST
Problem
Sorted keys have search frequencies. Build a BST that minimises the total search cost Σ frequency × depth (the root is at depth 1). Return that cost.
Example 1
Input: keys = [10, 12, 20], freq = [34, 8, 50] Output: 142
Also asked as: Optimal Binary Search Tree
Test cases
Case 1
Input: [34,8,50] Expected: 142
Case 2
Input: [34,50] Expected: 118
Case 3
Input: [1,1,1] Expected: 5
Case 4
Input: [5] Expected: 5
View solutionHide solution1 approach
1. Interval DP with prefix frequency sums
Time O(n³)Space O(n²)
dp[i][j] = min expected search cost for keys i..j. Try each key r as the root: dp[i][r−1] + dp[r+1][j] + (sum of freq i..j). Every subtree drops one level, so the whole range’s frequency sum is added once per split.
function optimalBST(freq) { const n = freq.length; const prefix = [0]; for (const f of freq) prefix.push(prefix[prefix.length - 1] + f); const rangeSum = (i, j) => prefix[j + 1] - prefix[i]; const dp = Array.from({ length: n }, () => new Array(n).fill(0)); for (let i = 0; i < n; i++) dp[i][i] = freq[i]; for (let len = 2; len <= n; len++) for (let i = 0; i + len - 1 < n; i++) { const j = i + len - 1; dp[i][j] = Infinity; for (let r = i; r <= j; r++) { const left = r > i ? dp[i][r - 1] : 0; const right = r < j ? dp[r + 1][j] : 0; dp[i][j] = Math.min(dp[i][j], left + right + rangeSum(i, j)); } } return dp[0][n - 1];}