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.

  • 1
    $\begingroup$ the problem seems to be closely related to balanced binary trees, have you looked into that theory? $\endgroup$
    – vzn
    Commented 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
    Commented 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$ Commented Mar 5, 2012 at 13:32


Your Answer

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