Log inSign up
hardGeeksforGeeksNot Started

Optimal Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a sorted array keys[0..n-1] of search keys and an array freq[0..n-1] of frequency counts, where freq[i] is the number of searches for keys[i].

Find the minimum cost of a binary search tree (BST) that contains all given keys.

The search cost of a BST node is defined as its level (depth + 1) multiplied by its frequency. The total cost of the BST is the sum of costs of all nodes.

### Example 1 - Input: keys = [10, 12, 20], freq = [34, 8, 50] - Output: 142 - Explanation: A tree with root 20, left child 10, and right child of 10 being 12: - Level of 20 = 1, cost = 50 * 1 = 50 - Level of 10 = 2, cost = 34 * 2 = 68 - Level of 12 = 3, cost = 8 * 3 = 24 - Total cost = 50 + 68 + 24 = 142.

### Example 2 - Input: keys = [10, 12], freq = [8, 50] - Output: 66 - Explanation: Root is 12 (level 1, cost 50), left child is 10 (level 2, cost 8 * 2 = 16). Total = 50 + 16 = 66.

Constraints:

  • 1 <= n <= 100
  • 1 <= keys[i] <= 105
  • 1 <= freq[i] <= 104
  • keys array is strictly sorted in ascending order

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate the Optimal BST recurrence and understand why frequencies sum adds at each tree level.
  • Use prefix sum arrays to evaluate range sums in O(1).
  • Implement interval DP tabulation with chain length outer loop.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Hierarchical BST structuring to minimize weighted search depth.
  • Contiguous sub-ranges [i, j] split by an optimal root r.

Algorithmic Decision Tree:

  • Precompute prefix sum array for freq.
  • Iterate over interval lengths from 1 to n.

Connected Patterns:

Matrix Chain MultiplicationMinimum Cost to Cut a StickBurst Balloons

1. Recursive Tree Partitioning

Intuition

Recursively try every key in the range [i, j] as the root of the subtree.

Algorithm

  1. Define solve(i, j).
  2. If i > j, return 0.
  3. If i == j, return freq[i].
  4. Calculate fSum = sum(freq[i..j]).
  5. For each r from i to j:
  6. minCost = min(minCost, solve(i, r - 1) + solve(r + 1, j)).
  7. Return fSum + minCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 int sumFreq(const vector<int>& freq, int i, int j) {
10 int s = 0;
11 for (int k = i; k <= j; ++k) s += freq[k];
12 return s;
13 }
14
15 int solve(int i, int j, const vector<int>& freq) {
16 if (i > j) return 0;
17 if (i == j) return freq[i];
18
19 int fSum = sumFreq(freq, i, j);
20 int minCost = 1e9;
21
22 for (int r = i; r <= j; ++r) {
23 int cost = solve(i, r - 1, freq) + solve(r + 1, j, freq);
24 minCost = min(minCost, cost);
25 }
26
27 return fSum + minCost;
28 }
29public:
30 int optimalSearchTree(vector<int>& keys, vector<int>& freq, int n) {
31 return solve(0, n - 1, freq);
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> keys = {10, 12, 20};
38 vector<int> freq = {34, 8, 50};
39 cout << "Optimal BST Cost: " << sol.optimalSearchTree(keys, freq, 3) << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(Catalan(n) * n) = O(4^n / sqrt(n))
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP with Prefix Sums

Intuition

Use a 2D memo table of size n x n and precomputed prefix sum array for O(1) frequency sums.

Algorithm

  1. Precompute prefix sums pref[k].
  2. Initialize memo[n][n] with -1.
  3. In solve(i, j): return memo[i][j] if already computed.
  4. Evaluate min cost across all candidate roots r.
  5. Save and return memo[i][j].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 int getSum(const vector<int>& pref, int i, int j) {
10 return pref[j + 1] - pref[i];
11 }
12
13 int solve(int i, int j, const vector<int>& freq, const vector<int>& pref, vector<vector<int>>& memo) {
14 if (i > j) return 0;
15 if (i == j) return freq[i];
16 if (memo[i][j] != -1) return memo[i][j];
17
18 int fSum = getSum(pref, i, j);
19 int minCost = 1e9;
20
21 for (int r = i; r <= j; ++r) {
22 int cost = solve(i, r - 1, freq, pref, memo) + solve(r + 1, j, freq, pref, memo);
23 minCost = min(minCost, cost);
24 }
25
26 return memo[i][j] = fSum + minCost;
27 }
28public:
29 int optimalSearchTree(vector<int>& keys, vector<int>& freq, int n) {
30 vector<int> pref(n + 1, 0);
31 for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + freq[i];
32
33 vector<vector<int>> memo(n, vector<int>(n, -1));
34 return solve(0, n - 1, freq, pref, memo);
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> keys = {10, 12, 20};
41 vector<int> freq = {34, 8, 50};
42 cout << "Optimal BST Cost: " << sol.optimalSearchTree(keys, freq, 3) << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^2) memo table + O(n) call stack

3. Iterative Bottom-Up Interval DP

Intuition

Tabulate optimal costs for intervals of length L = 1 to n using prefix sums.

Algorithm

  1. Initialize prefix sum array pref of size n + 1.
  2. Initialize dp[n][n] with 0.
  3. For i = 0 to n - 1: dp[i][i] = freq[i] (chains of length 1).
  4. Loop chain length L from 2 to n:
  5. Loop starting index i from 0 to n - L:
  6. j = i + L - 1.
  7. fSum = pref[j + 1] - pref[i].
  8. dp[i][j] = infinity.
  9. For root r from i to j:
  10. left = (r > i) ? dp[i][r - 1] : 0.
  11. right = (r < j) ? dp[r + 1][j] : 0.
  12. dp[i][j] = min(dp[i][j], fSum + left + right).
  13. Return dp[0][n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int optimalSearchTree(vector<int>& keys, vector<int>& freq, int n) {
11 vector<int> pref(n + 1, 0);
12 for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + freq[i];
13
14 vector<vector<int>> dp(n, vector<int>(n, 0));
15
16 for (int i = 0; i < n; ++i) dp[i][i] = freq[i];
17
18 for (int L = 2; L <= n; ++L) {
19 for (int i = 0; i <= n - L; ++i) {
20 int j = i + L - 1;
21 int fSum = pref[j + 1] - pref[i];
22 int minCost = 1e9;
23
24 for (int r = i; r <= j; ++r) {
25 int left = (r > i) ? dp[i][r - 1] : 0;
26 int right = (r < j) ? dp[r + 1][j] : 0;
27 minCost = min(minCost, left + right);
28 }
29
30 dp[i][j] = fSum + minCost;
31 }
32 }
33
34 return dp[0][n - 1];
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> keys = {10, 12, 20};
41 vector<int> freq = {34, 8, 50};
42 cout << "Optimal BST Cost: " << sol.optimalSearchTree(keys, freq, 3) << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^2)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Tree PartitioningO(4^n / sqrt(n))O(n)Recursively try every key as root.Catalan number of BST shapes
2.Top-Down Memoization + Prefix SumO(n^3)O(n^2)Cache subproblems (i, j) with O(1) interval sum lookup.O(n3) state transitions
3.Iterative Bottom-Up Interval DPOptimalO(n^3)O(n^2)Tabulate interval lengths from 1 to n.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Computing sum(freq[i..j]) inside the inner loop: makes runtime O(n4) instead of O(n3). Use prefix sums.

Pitfall 2:

Forgetting to check boundary conditions (r > i and r < j) when accessing left and right subtrees.

Crucial Edge Cases to Validate:

  • n = 1: Single key; returns freq[0].
  • Uniform frequencies: Equal frequency across all keys creates a balanced BST.
  • Monotonically increasing frequencies: Skewed BST where higher frequency elements stay near root.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that Knuth's Optimization can reduce the time complexity of Optimal BST from O(n3) to O(n2) by observing the monotonicity of the optimal root position: opt[i][j-1] <= opt[i][j] <= opt[i+1][j].

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the term sum(freq[i..j]) appear when choosing a root r for the sub-range [i, j]?

Back to DSA Sheet