# 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
Commented Jan 10, 2015 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). Commented Jan 22, 2015 at 20:36
• What have you tried so far? Have there been attempts on reductions? Commented Oct 26, 2018 at 13:34
• I believe the dynamic programming algorithm by Knuth for optimal binary search trees is close to what you want. Commented Aug 20, 2019 at 15:42
• @vonbrand Theres one huge difference of the elements being ordered in the problem statement for knuth's algo. Here the elements can be permuted to any way we want.
– EnEm
Commented 2 days ago

This problem has optimal substructure property, i.e., in an optimal tree $$T$$, trees $$T.l$$ and $$T.r$$ will also be optimal for their corresponding subset of leaves.
Then, lets say you have two polynomial time methods $$w, s: \mathcal{P}(W) \setminus \{\emptyset, W\} \rightarrow \mathbb{N}_0$$ which denote the $$W(T)$$ and $$I(T)$$ of the optimal tree for any proper subset $$H\subset W$$.
Then our task remains to find the subset $$H_0 \subset W$$ where $$s(W) = |w(H_0) - w(W\setminus H_0) | + s(H_0) + s(W\setminus H_0)$$ is $$\le k$$. This is very similar to the partition problem to be solvable in polynomial time. Idea is that there can be an adversary which fine tunes on the list $$W$$ and $$k$$ such that the above problem becomes ewuivalent to the partition problem.