# Is finding a weight-balanced tree NP-hard?

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and right child respectively.

We define the imbalance $I(T)$ of a binary tree $T$ as follows:

$$I(T) = \begin{cases} 0 & size(T) = 1\\ |W(T.l) - W(T.r)| + I(T.l) + I(T.r) & size(T)>0 \end{cases}$$

Examples

  a.)  *        b.)  *
/ \          /   \
*   5        *     *
/ \          / \   / \
*   3        1   5 3   3
/ \
1   3


Tree a. has imbalance 5 (2 + 1 + 2) and tree b. has imbalance 4 (4 + 0 + 0).

Consider the following problem:

Input: a list of $n$ positive integers $W = (a_1, \ldots, a_n)$, and an integer $k$.

Query: is there a binary tree $T$ with leaf weights $W$ such that $I(T) \leq k$?

Is this problem $\mathsf{NP}$-hard?

The case $k = 0$ is easy. There is a simple algorithm which goes as follows ($Q$ is a priority queue):

1. for $w \in W$: $Q.push(w)$
2. while $Q.size > 1$:
2.1. pop the two smallest elements $w_1$ and $w_2$ form $Q$.
2.2. if $w_1 = w_2$ then $Q.push(2*w_1)$
2.3. else return "No"
3. return "Yes"
• Just to rule out simple reduction - can you think of a case where the set of weights has equal-weight partition and the optimal tree doesn't partition the leafs accordingly? – R B Jan 10 '15 at 13:44
• @RB If I understand your comment correctly, $\{1,2,3,4\}$ would be an example. Equal weight partition gives [[1 4][2 3]] (imbalance 4) where as the optimal tree is [4 [3 [2 1]]] (imbalance 3). – rex123 Jan 22 '15 at 20:36
• What have you tried so far? Have there been attempts on reductions? – Gabriel Tigerström Oct 26 '18 at 13:34
• I believe the dynamic programming algorithm by Knuth for optimal binary search trees is close to what you want. – vonbrand Aug 20 '19 at 15:42