16
$\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.