6
$\begingroup$

I am not sure whether the following problem has been studied.

We have a undirected tree $T$. We would like to construct another tree $T'$. $T'$ is a binary tree. Each inner nodes of $T'$ is an edge of $T$. The set of leaves of $T'$ is the same as the set of leaves of $T$. $T'$ is constructed as follows:

We pick an edge $e$ in $T$, which breaks $T$ into two parts $T_1$ and $T_2$. $e$ is the root of T'. we recursively construct the left and right subtrees of T' from $T_1$ and $T_2$ respectively. The cost of T' is $\sum_{v:leaves}Length_{T'}(P_v)$ where $P_v$ is the path from the root to $v$. We would like to find the tree T' that minimizes the cost.

I suspect the optimal algorithm is to pick the edge which split the number of leaves as evenly as possible and recurse. However, it seems to be a clean problem that has been studied. But I have no idea what to search. Any help will be appreciated.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ the problem seems to be closely related to balanced binary trees, have you looked into that theory? $\endgroup$
    – vzn
    Mar 2, 2012 at 16:21
  • $\begingroup$ Thanks. I found the optimal binary search tree is a special case of my problem where $T$ is a path: en.wikipedia.org/wiki/… $\endgroup$
    – jian
    Mar 3, 2012 at 2:26
  • $\begingroup$ Well, you could just follow your recursive procedure, using memoization (i.e., a DP algorithm). That'd give you an algorithm that's polynomial in the number of subtrees in the tree, but how high that number is would depend on the structure of the tree, I guess. Still would be much faster than exhaustive search. $\endgroup$
    – Magnus Lie Hetland
    Mar 5, 2012 at 13:32

0

Reset to default

Your Answer

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