Binary Tree max sum conditionally

Question

Problem : A binary tree is given as an input, each node of binary tree contains one integer value. Find the maximum sum of collection of nodes such that following two conditions are met.

• if node's parent node is considered for sum, then node cannot be considered.
• if node's either of child is considered for sum, then node cannot be considered.

For example :

For a binary tree

             15
      20            25
   5      15      5  

The max sum we can get is considering [20, 25] which is 45.

To implement this I used O(n^2) approach and code is here.

I am trying to optimize it and looking for feedback on improving algorithm, code efficiency and cleanliness

tree is String representation of tree, given in BFS manner. _ is present in place of null element. _ is not given for the deepest level's element's null representation.

the above tree would be represented as 15 20 25 5 15 5 _

static int findMaxSum(String tree) {
    String[] tokens = tree.split(" ");
    int max = 0;
    for (int i = 0; i < tokens.length; i++) {
        if (!isValidToken(tokens[i])) {
            continue;
        }
        Set<Integer> set = new HashSet<>();
        //wildcard entry
        set.add(i);
        int sum = Integer.parseInt(tokens[i]);
        for (int j = 0; j < tokens.length; j++) {
            if (isValidToken(tokens[j])) {
                if(!set.contains(j) && !set.contains(getParentIndex(j))){
                    if (!set.contains(getLeftChildIndex(j)) && !set.contains(getRightChildIndex(j))) {
                        set.add(j);
                        sum += Integer.parseInt(tokens[j]);
                    }
                }
            }
        }
        max = Math.max(max,sum);
    }

    return max;
}


static boolean isValidToken(String token) {
    return !"_".equals(token);
}

static int getLeftChildIndex(int parentIndex) {
    return parentIndex * 2 + 1;
}

static int getRightChildIndex(int parentIndex) {
    return parentIndex * 2 + 2;
}

static int getParentIndex(int childIndex) {
    return (childIndex - 1)/2;
}

Note: this code works but it is not efficient. I am looking for ideas on how to improve it.

Answer 1

I think I understand the problem, which if I am not mistaken means we want to pick a set of nodes from the tree such that no two taken nodes are connected in the tree. If you just think about it in a recursive manner, you either take a node and neither of its children, recursively trying to solve the same problem with the grandchildren. Or you do not take the node, and take the sum of the same problem solved for both children. An implementation could look like this (I left out underscore, using the index to check for the end of the tree):

static int max(final String tree) {
    return max(0, stream(tree.split(" ")).mapToInt(Integer::parseInt).toArray());
}

static int max(final int root, final int... nodes) {
    if (root >= nodes.length) {
        return 0;
    }

    final int maxWithRoot =
            nodes[root]
            + max(getLeftChildIndex (getLeftChildIndex(root)),  nodes)
            + max(getRightChildIndex(getLeftChildIndex(root)),  nodes)
            + max(getLeftChildIndex (getRightChildIndex(root)), nodes)
            + max(getRightChildIndex(getRightChildIndex(root)), nodes);

    final int maxWithoutRoot = max(getLeftChildIndex(root),  nodes) + 
                               max(getRightChildIndex(root), nodes);

    return Integer.max(maxWithoutRoot, maxWithRoot);
}

You can now also see that the same calculation will be executed multiple times for the same node. But because the result of the max function only depends on the root index, you can cache the calculations, meaning you calculate the result for each node only once.

In this case, you could simply create an integer array as a cache, using the node index as the cache index.

Answer 2

If I understand the rules correctly, it can me implemented in O(N) in the following way:

1. Attach a second integer to each node
2. non-leaf node = 0, leaf node = node's main value.
3. Do a depth-first walk.
4. For every node that you visited all children of, set the second value to the sum of the second values of the direct children. If the second value is smaller than the main value, set it to the main value instead

(i adjusted 2nd leaf node from 15 to 10 for illustrative purposes)

After step 2.

          15
           0
   20            25
    0             0
5      10      5  
5      10      5  

After first non-leaf is visited:

          15
           0
   20            25
-> 15 <-          0
5      10  
5      10      5  

15 is smaller so set it to 20

          15
           0
   20            25
   20             0
5      10      5  
5      10      5  

Final tree after algorithm:

          15
          45 <- answer
   20            25
   20            25
5      10      5  
5      10      5