-2

I am working on a problem that calculates the minimum number of traversals required in a binary search tree by arranging it the best way possible. I did come across a solution online, which I have understood, but I did some calculations of sample inputs by hand, and I did not get the right result.

Following is the code

#include <stdio.h>
#include <limits.h>

// A utility function to get sum of array elements freq[i] to freq[j]
int sum(int freq[], int i, int j);

/* A Dynamic Programming based function that calculates minimum cost of
   a Binary Search Tree. */
int optimalSearchTree(int keys[], int freq[], int n)
{
    /* Create an auxiliary 2D matrix to store results of subproblems */
    int cost[n][n];

    /* 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 */

    // For a single key, cost is equal to frequency of the key
    for (int i = 0; i < n; i++)
        cost[i][i] = freq[i];

    // Now we need to consider chains of length 2, 3, ... .
    // L is chain length.
    for (int L=2; L<=n; L++)
    {
        // i is row number in cost[][]
        for (int i=0; i<=n-L+1; i++)
        {
            // Get column number j from row number i and chain length L
            int j = i+L-1;
            cost[i][j] = INT_MAX;

            // Try making all keys in interval keys[i..j] as root
            for (int r=i; r<=j; r++)
            {
               // c = cost when keys[r] becomes root of this subtree
               int c = ((r > i)? cost[i][r-1]:0) + 
                       ((r < j)? cost[r+1][j]:0) + 
                       sum(freq, i, j);
               if (c < cost[i][j])
                  cost[i][j] = c;
            }
        }
    }
    return cost[0][n-1];
}

// A utility function to get sum of array elements freq[i] to freq[j]
int sum(int freq[], int i, int j)
{
    int s = 0;
    for (int k = i; k <=j; k++)
       s += freq[k];
    return s;
}

// Driver program to test above functions
int main()
{
    int keys[] = {10, 12, 20};
    int freq[] = {34, 8, 50};
    int n = sizeof(keys)/sizeof(keys[0]);
    printf("Cost of Optimal BST is %d ", optimalSearchTree(keys, freq, n));
    return 0;
}

For instance for the input int keys[] = {1,2,3}; int freq[] = {10,3,1};

I SHOULD GET 18 but i GET 19

FOR THIS INPUT int keys[] = {1,2,3,4}; int freq[] = {5,4,1,200};

I SHOULD GET 225 I GET 226

FOR THIS INPUT int keys[] = {1,2,3,4,5,6}; int freq[] = {33,1,409,2,1,34};

I SHOULD GET 997 but I GET 556

For This Input int keys[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; int freq[] = {5,5,5,5,5,5,5,5,5,5,167,5,5,5,5,5,5,5,5,5};

I Should Get 789 but i GET 532

What is wrong?

6
  • Could you please explain what these values keys and freq represent and the algorithm you are trying to apply ?
    – chmike
    Mar 12, 2015 at 13:11
  • @chmike This is a good source webcache.googleusercontent.com/… Mar 12, 2015 at 13:17
  • When you used the debugger, and single stepped through your code, which lines are presenting issues? Mar 12, 2015 at 13:34
  • for the case: int keys[] = {1,2,3}; int freq[] = {10,3,1}; the result should be 19
    – simon_xia
    Mar 12, 2015 at 14:06
  • suppose you have three terms, A, B, and C. You search for A 10 times, B 3 times, and C 1 time. You could arrange them with A on the left branch, and B and C as a pair on the right branch. In terms of the number of edges you have to traverse to handle all the searches, there are 10 traversals of a single edge to get to A, and then 4 traversals of the edge to get to the B and C pair, and then 3 down the edge to B, and 1 down the edge to C. The total number of edge traversals for this tree is 10 + 4 + 3 + 1, or 18. Mar 12, 2015 at 14:52

1 Answer 1

2

You are mistaken about the results to expect. Take your first example, with keys {1, 2, 3} and frequencies {10, 3, 1}; the optimal binary search tree is:

  1 (10)
   \
    2 (3)
     \
      3 (1)

(frequencies given in parentheses). The function returns the expected cost for seaching the tree sum(frequencies) times, as measured by the number of nodes visited, and it is (10 * 1) + (3 * 2) + (1 * 3) = 19. Each search for key 1 traverses only the root node. Each search for key 2 traverses the root node, finding the target key in its child node, for a total of two nodes traversed. Similarly, each search for key 3 traverses three nodes.

It makes sense to measure cost in terms of nodes visited, because a comparison must be made against each visited node's key, but you can also measure cost in terms of edges traversed. The result is identical, however, if you count an edge incoming to the root, representing the host program's pointer to the tree. In that case, every node visit involves traversing that node's incoming edge, erasing any distinction between counting cost in terms of node visits or edge traversals.

With keys {1,2,3,4} and frequencies {5,4,1,200}, the optimal binary search tree is

    4 (200)
   /
  1 (5)
   \
    2 (4)
     \
      3 (1)

with a cost of (200 * 1) + (5 * 2) + (4 * 3) + (1 * 4) = 226.

With keys {1,2,3,4,5,6} and frequencies {33,1,409,2,1,34}:

            3 (409)
          /     \
         /       \
        1 (33)    6 (34)
         \       /
          2 (1)  4 (2)
                  \
                   5(1)

with cost (409 * 1) + ((33 + 34) * 2) + ((1 + 2) * 3) + (1 * 4) = 556.

The program returns the correct result in each case.

I leave the 20-key example as an exercise for you. There are multiple optimal search trees for that case, but all have cost 532, as given by the program.

9
  • suppose you have three terms, A, B, and C. You search for A 10 times, B 3 times, and C 1 time. You could arrange them with A on the left branch, and B and C as a pair on the right branch. In terms of the number of edges you have to traverse to handle all the searches, there are 10 traversals of a single edge to get to A, and then 4 traversals of the edge to get to the B and C pair, and then 3 down the edge to B, and 1 down the edge to C. The total number of edge traversals for this tree is 10 + 4 + 3 + 1, or 18. Mar 12, 2015 at 14:43
  • @user2733436, the program counts node visits, which is a valid cost measure. It is equivalent to counting edge traversals if and only if you include an incoming edge to the root node in your counts (and it makes sense to do so, else searches for the key stored in the root node are accounted free). Ignoring the question of what keys are stored in the root and right-hand child nodes of your tree, the number of node visits required to search it is (10 * 2) + ((4 + 3) * 3) = 56, much worse than the tree I presented. Mar 12, 2015 at 14:59
  • @user2733436, even if you count edge traversals, and even if you don't count an edge traversal to reach the root, you have counted wrongly for your tree. You must count 1 edge traversal for each search for key A, and two for each search for B or C -- one from root to its right-hand child, and another from there to the target node. That makes 10 + (4 + 3) * 2 = 24, still worse than my tree (value 18 if you count it that way). Mar 12, 2015 at 15:06
  • @user2733436, in any event, the question is about why the program's output does not agree with the OP's expectation, and I have answered that with an accurate description of what the program is doing. You are free to disapprove of the cost measure it uses, but that's irrelevant to the question. Mar 12, 2015 at 15:08
  • @user2733436, I expressly gave a count of the number of node visits involved in searching the tree, and it is certainly 19, as I said. The computation is given in the answer. That is also the number of edge traversals required to search the tree, supposing that you count an incoming edge to the root node. If you don't count an incoming edge to the root, then the search cost is (10 * 0) + (3 * 1) + (1 * 2) = 5. Mar 12, 2015 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.