# Dynamic Programming, Binary Tree: How to factor in depth to recursion?

I have the following problem.

I have a set of elements $x_0,\ldots,x_n$ which must retain their order inside the binary tree: if, given $x_i, x_j, i < j$, $x_i$ must be to the left of $x_j$ if $x_j$ is the root and $x_i$ is part of $x_j$'s subtree.

I also have a set of frequencies $f_0,\ldots,f_n$. I need to build a binary tree such that the cost of accessing the elements, defined as $depth$*$f$ is minimized.

I figured this was just like chain matrix multiply, so I wrote that the dynamic table was:

T(i,j) = minimum cost tree between i and j


And I wrote the following recurrence:

$$T(i,j) = min \lbrace T(i,k) + T(k,j)\rbrace, i \le k < j$$

However, I can't figure out if depth is being factored in here--it appears (to me) that it isn't.

How do I construct this recurrence??

• What do you mean by $depth*f$? Do you mean the cost of accessing the $i$th item is $depth * f_i$? What do you mean by "the cost of accessing the elements"? It sounds like the cost depends on which element you are accessing. Do you mean the average/expected cost? If so, what is the distribution on element accesses you are assuming? What have you tried? This is a nice exercise, but we don't want to just solve exercises for you. Try writing down an argument that your recurrence is correct. If you can't argue it, maybe that's a sign that you need a different recurrence. – D.W. Jan 31 '17 at 21:59
• @D.W. Thanks, and yeah--I get it. However, turns out that where I was confused had basically nothing to do with the problem. The confusion arose from what I thought I was "allowed" and "not allowed" to do in creating a solution to a dynamic programming problem (which is not at all clear, IMO, from the outside looking in). Very frustrated...feels very much like obfuscated easy math (long veteran of obfuscated, but easy, advanced math). Very frustrated. (Test next week if you can't tell :) – Chris Feb 1 '17 at 13:40

Turns out that I had a misunderstanding of the scope of dynamic programming. As I understood it, I was "not allowed" to capture other things outside the recursion besides elementary operations.

So, I just have to literally calculate the sum of values lower than the root on either side to factor in the depth:

$$T(i,j) = \sum_{i\leq l < j}f_l + min\lbrace + T(i,k-1) + T(k+1,j)\rbrace: i<k<j$$

Where I can just calculate the sum outside of the recursion.

If the aim is to build a data-structure that will minimize the access cost, which is defined as $height(tree)*f$, I would start with thinking about how to minimize this "already defined" cost.

• If you have repeating elements, and if the cost is dependent on the frequency, what should be the structure of the leaves?

• How can you minimize the height? Does the tree need to be binary? Which distribution of elements in the tree ensures easiest access? Which properties should the tree hold, in order to have minimum height?

• After you decide on the leaf and tree structure, how can you improve upon the dependency on $f$? Can you go beyond $f$ (not as in computational complexity, but for practical uses, i.e., $f/2$)?

I hope these questions hints towards the solution.