Redirecting to
NADOS


  Prev   Next

Optimal Binary Search Tree (BST)







Simplicity is prerequisite for reliability.
~Edsger W. Dijkstra

Optimal Binary Search Tree (BST)

Welcome back, dear reader. So, how is it going? In this article, we will discuss a very interesting and famous problem of dynamic programming called the OPTIMAL BINARY SEARCH TREE. So, let us have a look at the problem and try to understand what the problem wants from us.


Important Links : Problem Link, Solution Video


Understanding the Problem:

We will be given 2 arrays in the input. The first array will contain the data of the nodes and the second array will denote their search frequencies i.e. the number of times they have been searched in the Binary Search Tree (BST) formed by the nodes given in the first array. We have to find the Optimal BST which is defined as a BST that has the least cost of searching the elements.

Cost of Searching one Node:

The cost of searching one node is defined as the height of the node in the Binary Search Tree multiplied by the frequency of searching that node.

Cost of BST

The cost of a BST is the sum of the cost of searching every node in the BST.

Let us take an example to understand the question in a better way.

Example:

Let us say we have 3 nodes {10,20,30} and the frequency array is given as {5,2,6} i.e. the node 10 is searched 5 times and the node 20 is searched 2 times and node 30 is searched 6 times in the BST. We know that we can make 5 BSTs from 3 nodes (Catalan Number). So, the cost of each binary tree is shown below (in img-1).

So, out of them, we can say that the BST with cost 22 is the optimal Binary Search Tree(BST).

img

We don't have to display the tree. We just have to tell the minimum cost that we can have out of many BSTs that we can make from the given nodes.

We recommend you refer to the OPTIMAL BINARY SEARCH TREE VIDEO to understand the question properly and clear your doubts regarding the questions if any. We also suggest that you try to solve the problem on your own first and then refer to the solution to build your concepts stronger.

Approach:

Time Complexity: O(n2) where n is the number of nodes

Space Complexity: O(n2)

Explanation:

So, first of all, you need to remember that we can make a Catalan Number of BSTs if n nodes are given to us. For instance, if we have 4 nodes {a,b,c,d} then we can make 14 BSTs (14 is the 4th Catalan Number). This is shown in the figure below:

img

So, we hope that you remember this as we will not discuss the Catalan Numbers in this article. If you have any doubts regarding this, you may refer to the NUMBER OF BSTs VIDEO to understand this concept.

So, out of so many BSTs, we have to find the BST with the minimum cost of the search. So, let us start with our dynamic programming procedure.

  1. Storage and Meaning:
    First of all, we have to assign storage and some meaning to the storage that we have assigned. Let's start by taking an abstract example i.e. let us not consider any values for now. Let's say that we have an array of nodes {a,b,c,d} and the search frequencies of these nodes are in the second array i.e. {fa,fb,fc,fd}. So, let's start by making a matrix of size n x n where n is the number of nodes.
    img
    Now, we will use the gap strategy to fill this matrix initially. Since we are using the gap strategy, you already know what each cell will store and that the lower triangular half of the matrix is invalid and won't be used.
    img
  2. The direction of Solving:
    Since we know the meaning of each cell of the matrix and we also know that the number of BSTs generated is equal to the nth Catalan Number which depends upon the previous Catalan Numbers, we should start solving from the first element i.e. dp[0][0]. In each diagonal, we have an equal number of nodes for creating BST so, let us solve this problem diagonally. We will start from the main diagonal and reach other diagonals in the upper triangle of the matrix.
    Also, we will skip the invalid cells in this process. One more important thing is that we can already fill the main diagonal of this matrix. How? In the diagonal, the elements are of the form dp[i][j] where i=j. So, the main diagonal elements represent the minimum cost of the search for a BST, when the BST is only made of one node and that is the node represented by that particular row or column. Why? Think!!!
    So, the cost can be filled directly from the nodes array i.e. dp[i][j] (when i=j) = nodes[i].
    img
  3. Traverse and Solve
    So, let us now start traversing this matrix and solving it. We will first be at dp[0][1]. Here, we have to store the minimum cost of a BST that can be formed using the nodes "a" and "b". We can make the following 2 trees using the nodes "a" and "b".
    img
    Note: In the diagrams, we have depicted the frequencies in the formulas also by "a","b","c", and "d". So, don't get confused about that. In the frequency array, we have shown them as "fa", "fb" and so on.
    So, at dp[0][1], we will store the minimum cost of a BST formed by the nodes "a" and "b". The formula is generated by multiplying the height of the nodes in the BST with their frequencies shown in the frequency array. For now, we have depicted the frequency of "a" as only and not "fa" and so on for every node.
    img

If you think carefully, the same will happen for this entire diagonal as in this diagonal we have all the elements representing the BSTs formed by 2 nodes.

So, let us fill this complete diagonal.

img

Now, let us move to the element dp[0][2]. Here, we have to store the minimum cost of the BSTs formed by the nodes "a", "b", and "c".

img

So, we have to find the minimum cost of the trees formed by the nodes "a", "b", and "c".

Have a look at the first tree shown in the image above. We have two nodes "b" and "c" left in the right subtree. Now, the problem here is not to generate all the BSTs, but rather only to find the minimum cost. So, we will not generate the subtrees.

We can say that the cost of BST when "a" is the root is 0 + min(bc). The 0 here indicates that the cost of the left subtree is 0 since there are no nodes there and min(bc) denotes the minimum cost of the tree formed by nodes "bc". But is this the total cost of BST? The answer is "NO". Why?

Have a look at the diagram shown below (img-10)

It shows the complete BST when it is made using the two trees formed by the nodes "b" and "c". The difference between them is that when we form the complete tree, the depth of the nodes "b" and "c" has increased by 1 as we have "a" at the root of the tree. So, the cost will be affected. Also, we have not included the cost of the root node above.

So, we have to include one "a" i.e. frequency of searching for "a" and one "b" and "c" too. Therefore we add a+b+c to the minimum cost of the tree formed by the nodes "b" and "c" to obtain the minimum cost of the tree formed by the nodes "a", "b", and "c".

img

So, we now have the minimum cost out of all the trees that can be formed by keeping "a" as the root. We can find the same for both the other trees as well and the minimum out of them will be stored in dp[0][2].

Where to find the minimum cost of the subtrees?

You saw that we have to add a+b+c to the minimum cost of the subtrees to get the minimum cost of the current tree. But, where do we find the minimum cost of the subtrees?

Have a look at the image given below. We are depicting the spots in the matrix from where we can get the min costs of the subtrees that we require for each tree.

img

The first tree in the left of the matrix has an orange dot near it meaning that the cells highlighted in the matrix with orange, depict the min costs required. So, it needs 0 which is depicted outside the 0th row and it needs min(bc) which is depicted in the dp[1][2] while we are trying to fill dp[0][2]. These two elements lie in the diagonal before the current diagonal we are in.

You can observe the same for the rest of the two trees as well. So, we will get our elements from the diagonal and hence we were right in the beginning thinking about solving this problem diagonally.

So, we hope that you have understood now what we have to do and also why we are adding (a+b+c) to the previous subtrees minimum costs.

We highly recommend you refer to the solution video to understand this procedure in-depth. We also recommend you try to solve this problem for the following numeric values.

nodes[4]= {10,20,30,20}

freq[4]= {3,1,2,1}

The complete matrix is shown below and the procedure for these numeric values is also given in the solution video.

img

Now that we have understood the procedure, let us write the code for the same.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] keys = new int[n]; for (int i = 0; i < n; i++) { keys[i] = scn.nextInt(); } int[] frequency = new int[n]; for (int i = 0; i < n; i++) { frequency[i] = scn.nextInt(); } optimalbst(keys, frequency, n); } private static void optimalbst(int[] keys, int[] frequency, int n) { // make prefix sum of frequencies int[] fsum = new int[n]; for (int i = 0; i < n; i++) { if (i == 0) { fsum[i] = frequency[i]; } else { fsum[i] = frequency[i] + fsum[i - 1]; } } int[][] cost = new int[n][n]; for (int gap = 0; gap < n; gap++) { int si = 0; int ei = gap; while (ei < n) { if (gap == 0) { // diagonal cost[si][ei] = frequency[si]; } else if (gap == 1) { int sum = fsum[ei]; if (si - 1 >= 0) { sum -= fsum[si - 1]; } cost[si][ei] = Math.min(cost[si][ei - 1], cost[si + 1][ei]) + sum; } else { cost[si][ei] = Integer.MAX_VALUE; int sum = fsum[ei]; if (si - 1 >= 0) { sum -= fsum[si - 1]; } for (int i = si; i < ei - 1; i++) { cost[si][ei] = Math.min(cost[si][i] + cost[i + 2][ei] + sum, cost[si][ei]); } cost[si][ei] = Math.min(Math.min(cost[si][ei - 1], cost[si + 1][ei]) + sum, cost[si][ei]); } si++; ei++; } } System.out.println(cost[0][n - 1]); } }
java; true";

The above code is explained in the solution video. We recommend you refer to it to understand the code in-depth and clear all your doubts regarding it if any. Let us now discuss the time and space complexity of this code.

Analysis
Time Complexity:

The time complexity of this code is O(n2) as we are traversing a matrix of size n x n. Although we are traversing the upper triangular half only, the time complexity will be O(n2) only. Why? Think!!!

Space Complexity:

The space complexity will be O(n2) because we have created a dp matrix of size n x n.

So, dear reader, we hope that you have got the complete solution. We highly recommend you refer to the complete solution video once to clear all your doubts and understand this concept in more depth and with more analysis of every step. With this, we have completed this problem.

Suggestions:

Here are a few suggestions from our side that you do not want to miss:

  1. We recommend you refer to the NUMBER OF BSTs video first if you do not know that we can generate a Catalan number of n BSTs if we are provided with n nodes. We have explained the relation of Catalan Numbers and BSTs in great depth in that video.
  2. We also suggest that you refer to the complete solution video once as these are difficult questions and concepts. They will be better understood by you if you watch the video and then refer to the article or do both of them simultaneously. Only reading the article won't help that much here. So, keep practicing and working hard. Till then, Happy Coding!!!!
Optimal Binary Search Tree
Dynamic Programming and Greedy
Author: Guneet Malhotra
 
Run
Id Name