# Optimal Binary Search Tree

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 to *keys\[i]*. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

Let us first define the cost of a BST. The cost of a BST node is level of that node multiplied by its frequency. Level of root is 1.

**Examples:**

```
Input:  keys[] = {10, 12}, freq[] = {34, 50}
There can be following two possible BSTs 
        10                       12
          \                     / 
           12                 10
          I                     II
Frequency of searches of 10 and 12 are 34 and 50 respectively.
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118 


Input:  keys[] = {10, 12, 20}, freq[] = {34, 8, 50}
There can be following possible BSTs
    10                12                 20         10              20
      \             /    \              /             \            /
      12          10     20           12               20         10  
        \                            /                 /           \
         20                        10                12             12  
     I               II             III             IV             V
Among all possible BSTs, cost of the fifth BST is minimum.  
Cost of the fifth BST is 1*50 + 2*34 + 3*8 = 142
```

```java
class solution {
    // Here array keys[] is assumed to be sorted in
    // increasing order. This means when we make left and right fn calls then the
    // keys will be in correct places (as they are already sorted)
    // If keys[] is not sorted, then
    // add code to sort keys, and rearrange freq[] accordingly.
    public static int optimalSearchTree(int[] keys, int[] freq, int n) {

        int[][] cost = new int[n][n];
        // Stores sum of frequency array between i & j
        int[][] prefixSum = new int[n][n];
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += freq[j];
                prefixSum[i][j] = sum;
            }
        }
        /*
         * cost[i][j] = Optimal cost of binary search tree that can be formed from
         * keys[i] to keys[j]. cost[0][n-1] will store the resultant cost
         */
        // i and j are start and end pointers between which we are working
        // Base case when i=j
        for (int i = 0; i < n; i++)
            cost[i][i] = freq[i];
        // Diagonal base case
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                cost[i][j] = Integer.MAX_VALUE;
                // Consider all the elements in between as root node
                for (int r = i; r <= j; r++) {
                    // Adding additional layer of prefixSum, because all the node in left and right subtree
                    // will be at a lower level in this tree, therefore their multiplier increases by 1
                    cost[i][j] = Math.min(cost[i][j], (r > i ? cost[i][r - 1] : 0) + (r < j ? cost[r + 1][j] : 0) + prefixSum[i][j]);
                }
            }
        }
        return cost[0][n - 1];
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/optimal-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.