Optimal Binary Search Tree Hard 0 attempts
GeeksforGeeks ↗

Optimal Binary Search Tree

Hard Dynamic ProgrammingMemoization GeeksforGeeks

You're given a sorted list of keys along with how frequently each one is searched for. Arrange these keys into a binary search tree so that the total search cost — each key's frequency multiplied by its level in the tree (the root is at level 1) — is as low as possible. Return that minimum cost as an integer.

Input Format
Implement optimalBST(keys, freq). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
keys = [10,12,20]
freq = [34,8,50]
Output
142

Example 2

Input
keys = [10]
freq = [5]
Output
5
Constraints
  • 1 <= keys.length == freq.length <= 50
  • Keys are distinct and sorted in increasing order.
  • Frequencies are non-negative integers, and the cost fits in a safe JavaScript integer.
Test Cases (2)
Case 1
Args: [[10,12,20],[34,8,50]] Expected: 142
Case 2
Args: [[10],[5]] Expected: 5
Topics
Dynamic ProgrammingMemoization

Interval Dynamic Programming

javascript
function optimalBST(keys, freq) {
  const n = keys.length;
  const dp = Array.from({length:n}, ()=>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;
      let sum = 0; for (let k = i; k <= j; k++) sum += freq[k];
      for (let r = i; r <= j; r++) {
        const cost = sum + (r>i?dp[i][r-1]:0) + (r<j?dp[r+1][j]:0);
        dp[i][j] = Math.min(dp[i][j], cost);
      }
    }
  }
  return dp[0][n-1];
}

Time: O(n³) | Space: O(n²)

Saved in this browser only. Private to you.

JavaScript