<p>I am not sure whether the following problem has been studied.</p>

<p>We have a undirected tree $T$.
We would like to construct another tree $T&#39;$.
$T&#39;$ is a binary tree. Each inner nodes of $T&#39;$ is an edge of $T$.
The set of leaves of $T&#39;$ is the same as the set of leaves of $T$.
$T&#39;$ is constructed as follows:</p>

<p>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&#39;}(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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-05T13:32:00.877Z
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.
Magnus Lie Hetland
CC BY-SA 3.0
2012-03-02T16:21:18.263Z
the problem seems to be closely related to [balanced binary trees](http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree), have you looked into that theory?
vzn
CC BY-SA 3.0
2012-03-03T02:26:43.353Z
Thanks. I found the optimal binary search tree is a special case of my problem where $T$ is a path: http://en.wikipedia.org/wiki/Binary_search_tree#Optimal_binary_search_trees
jian
<ds.algorithms><reference-request><coding-theory><decision-trees>
Tree rotation, a problem similar to Huffman coding
jian
# Tree rotation, a problem similar to Huffman coding

(Asked by: username_0 on 2012-03-02)

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.

**Tags:** ds.algorithms, reference-request, coding-theory, decision-trees

> **Comments:**
> **username_2**: the problem seems to be closely related to [balanced binary trees](http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree), have you looked into that theory?  
> **username_0**: Thanks. I found the optimal binary search tree is a special case of my problem where $T$ is a path: http://en.wikipedia.org/wiki/Binary_search_tree#Optimal_binary_search_trees  
> **username_1**: 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.  

---

## 0 answers

