title: Finding size of max independent set in binary tree - why faulty "solution" doesn't work?
body: <p>Here is a link to a similar question with a good answer: <a href="https://stackoverflow.com/questions/1567532/java-algorithm-for-finding-the-largest-set-of-independent-nodes-in-a-binary-tree">Java Algorithm for finding the largest set of independent nodes in a binary tree</a>.</p>
  
  <p>I came up with a different answer, but my professor says it won't work and I'd like to know why (he doesn't answer email).</p>
  
  <p>The question:</p>
  
  <blockquote>
    <p>Given an array A with n integers, its indexes start with 0 (i.e, <code>A[0]</code>,
    <code>A[1]</code>, …, <code>A[n-1]</code>). We can interpret A as a binary tree in which the two
    children of <code>A[i]</code> are <code>A[2i+1]</code> and <code>A[2i+2]</code>, and the value of each
    element is the node weight of the tree. In this tree, we say that a
    set of vertices is "independent" if it does not contain any
    parent-child pair. The weight of an independent set is just the
    summation of all weights of its elements. Develop an algorithm to
    calculate the maximum weight of any independent set.</p>
  </blockquote>
  
  <p>The answer I came up with used the following two assumptions about independent sets in a binary tree:</p>
  
  <ol>
  <li>All nodes on the same level are independent from each other.</li>
  <li>All nodes on alternating levels are independent from each other (there are no parent/child relations)</li>
  </ol>
  
  <p>Warning: I came up with this during my exam, and it isn't pretty, but I just want to see if I can argue for at least partial credit.</p>
  
  <p>So, why can't you just build two independent sets (one for odd levels, one for even levels)?</p>
  
  <p>If any of the weights in each set are non-negative, sum them (discarding the negative elements because that won't contribute to a largest weight set) to find the independent set with the largest weight.</p>
  
  <p>If the weights in the set are all negative (or equal to 0), sort it and return the negative number closest to 0 for the weight.</p>
  
  <p>Compare the weights of the largest independent set from each of the two sets and return it as the final solution. </p>
  
  <p>My professor claims it won't work, but I don't see why. Why won't it work?</p>