Finding size of max independent set in binary tree - why faulty "solution" doesn't work?

Question

Here is a link to a similar question with a good answer: Java Algorithm for finding the largest set of independent nodes in a binary tree.

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).

The question:

Given an array A with n integers, its indexes start with 0 (i.e, A[0], A[1], …, A[n-1]). We can interpret A as a binary tree in which the two children of A[i] are A[2i+1] and A[2i+2], 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.

The answer I came up with used the following two assumptions about independent sets in a binary tree:

1. All nodes on the same level are independent from each other.
2. All nodes on alternating levels are independent from each other (there are no parent/child relations)

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.

So, why can't you just build two independent sets (one for odd levels, one for even levels)?

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.

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.

Compare the weights of the largest independent set from each of the two sets and return it as the final solution.

My professor claims it won't work, but I don't see why. Why won't it work?

Answer 1

Interjay has noted why your answer is incorrect. The problem can be solved with a recursive algorithm find-max-independent which, given a binary tree, considers two cases:

1. What is the max-independent set given that the root node is included?
2. What is the max-independent set given that the root node is not included?

In case 1, since the root node is included, neither of its children can. Thus we sum the value of find-max-independent of the grandchildren of root, plus the value of root (which must be included), and return that.

In case 2, we return the max value of find-max-independent of the children nodes, if any (we can pick only one)

The algorithm may look something like this (in python):

def find_max_independent ( A ):
    N=len(A)

    def children ( i ):
        for n in (2*i+1, 2*i+2):
            if n<N: yield n

    def gchildren ( i ):
        for child in children(i):
            for gchild in children(child):
                yield gchild

    memo=[None]*N

    def rec ( root ):
        "finds max independent set in subtree tree rooted at root. memoizes results"

        assert(root<N)

        if memo[root] != None:
            return memo[root]

        # option 'root not included': find the child with the max independent subset value
        without_root = sum(rec(child) for child in children(root))

        # option 'root included': possibly pick the root
        # and the sum of the max value for the grandchildren
        with_root =  max(0, A[root]) + sum(rec(gchild) for gchild in gchildren(root))

        val=max(with_root, without_root)
        assert(val>=0)
        memo[root]=val

        return val


    return rec(0) if N>0 else 0

Some test cases illustrated:

tests=[
    [[1,2,3,4,5,6], 16], #1
    [[-100,2,3,4,5,6], 6], #2
    [[1,200,3,4,5,6], 200], #3
    [[1,2,3,-4,5,-6], 6], #4
    [[], 0],
    [[-1], 0],
]

for A, expected in tests:
    actual=find_max_independent(A)
    print("test: {}, expected: {}, actual: {} ({})".format(A, expected, actual, expected==actual))

Sample output:

test: [1, 2, 3, 4, 5, 6], expected: 16, actual: 16 (True)
test: [-100, 2, 3, 4, 5, 6], expected: 15, actual: 15 (True)
test: [1, 200, 3, 4, 5, 6], expected: 206, actual: 206 (True)
test: [1, 2, 3, -4, 5, -6], expected: 8, actual: 8 (True)
test: [], expected: 0, actual: 0 (True)
test: [-1], expected: 0, actual: 0 (True)

Test case 1

Test case 2

Test case 3

Test case 4

The complexity of the memoized algorithm is O(n), since rec(n) is called once for each node. This is a top-down dynamic programming solution using depth-first-search.

(Test case illustrations courtesy of leetcode's interactive binary tree editor)

Answer 2

Your algorithm doesn't work because the set of nodes it returns will be either all from odd levels, or all from even levels. But the optimal solution can have nodes from both.

For example, consider a tree where all weights are 0 except for two nodes which have weight 1. One of these nodes is at level 1 and the other is at level 4. The optimal solution will contain both these nodes and have weight 2. But your algorithm will only give one of these nodes and have weight 1.