# How to build an optimal tree given items costs and edge costs?

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?

• You seem to have have left something out: what constraint do you have on your trees such that you're searching through all possible trees? Mar 19, 2017 at 16:26
• @walpen I have added the sentence "We want to find the tree with the lowest cost". Does that clarify it, or do you mean something else?
– Qqwy
Mar 19, 2017 at 17:13
• I'm probably missing something here, but isn't a balanced tree the one with the least number of edges and thus the one with the minimal total cost? Mar 19, 2017 at 18:26
• @DanielJour The 'total cost' does not change between a balanced tree and an unbalanced one, as the amount of edges remains the same. But the maximum of (leaf node cost + edges up to root cost) does change.
– Qqwy
Mar 19, 2017 at 19:38
• The amount of edges is not the same: consider two leaves. Case one: a root node holding the two leaves. Two edges. Case two: a single inner node below root holding the two leaves. Three edges. Mar 19, 2017 at 19:51