Given:
- a list of 'leaves' that each have a cost,
- the cost of creating an 'edge'
- The constraint that a constructed tree node can at most have two children.
We now want to find the tree with the lowest maximum cost when adding up the cost of edges from each leaf up to the root node.
When naïvely attempting to build all different possible binary trees, one sees that this takes O(C(n))
steps, where C(n) is the n
-th Catalan Number
A simple dynamic programming-solution is isomorph with solving the Matrix Chain Multiplication Ordering problem, but filling the matrix used by this algorithm will take a ridiculous amount of memory.
I expect that it is possible to find a solution that is a lot more efficient (both in terms of time and memory).
How can you find out what the optimal tree structure would be?
How can you determine what the highest cost (cost of the leaf node + cost of the edges between it and the root node) would be in such a tree?