15
$\begingroup$

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"
$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – R B Jan 10 '15 at 13:44
  • 3
    $\begingroup$ @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). $\endgroup$ – rex123 Jan 22 '15 at 20:36
  • $\begingroup$ What have you tried so far? Have there been attempts on reductions? $\endgroup$ – Gabriel Tigerström Oct 26 '18 at 13:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.