ansaurus

Question

Java Algorithm for finding the largest set of independent nodes in a binary tree

Answer 1

+3 A:

You can compute this recursive function with dynamic programming (memoization):

MaxSet(node) = 1 if "node" is a leaf
MaxSet(node) = Max(1 + Sum{ i=0..3: MaxSet(node.Grandchildren[i]) },  
                       Sum{ i=0..1: MaxSet(node.Children[i])      })

The idea is, you can pick a node or choose not to pick it. If you pick it, you can't pick its direct children but you can pick the maximum set from its grandchildren. If you don't pick it, you can pick maximum set from the direct children.

If you need the set itself, you just have to store how you selected "Max" for each node. It's similar to the LCS algorithm.

This algorithm is O(n). It works on trees in general, not just binary trees.

Mehrdad Afshari 2009-10-14 16:47:59

This computes the size of the largest set, not the set itself.

Svante 2009-10-14 16:56:32

I need to return the actual node's, not just max. I will edit my post.

Algific 2009-10-14 16:58:56

Edited to compute the actual set.

Mehrdad Afshari 2009-10-14 17:05:17

This looks really nice, but this is really advanced. Sum and max I haven't seen before, and I don't directly see how I would store the value to retrieve the set?

Algific 2009-10-14 17:29:36

i=0..3: MaxSet(node.Grandchildren[i])i=0..1: MaxSet(node.Children[i]) Could you or someone explain this bit for me?

Algific 2009-10-14 17:31:23

data_jepp: It's not a standard notation, of course. I couldn't type a sigma there :) `Max` simply gets the maximum of two items. You'd use a `HashMap` or add a field to your node class that stores whether you select the node, or choose to select its children.

Mehrdad Afshari 2009-10-14 17:37:03

`MaxSet` is the function you are declaring, by the way. It's a simple dynamic programming problem. See http://en.wikipedia.org/wiki/Dynamic_programming if you are not familiar with it.

Mehrdad Afshari 2009-10-14 17:38:31

thank you for that!

Algific 2009-10-14 17:43:05

Im so sorry, I still dont get the i's. Why 0..3 and 0..1?

Algific 2009-10-14 17:57:37

The index doesn't really matter. If you select a node, you can select all its grand children (at most 4, thus 0..3). If you don't, you can select its direct children (at most 2, thus 0..1).

Mehrdad Afshari 2009-10-14 18:04:59

Ok, makes sense. But how would you do the actually storing of the nodes. Lets say the set is an ArrayList, were in the code above would I add an independent node to the independent set?

Algific 2009-10-14 20:25:32

In the algorithm, you'll just mark the operand you selected as max for each node. When the whole thing is done, you start at the root and check the direction you should go (it'll tell you whether you should add the root node to the list or not). It also tells you what nodes you should visit afterwards (if selected, you'll do the same thing recursively on grandchildren, otherwise you'll do it on children).

Mehrdad Afshari 2009-10-14 20:37:39

If I need to run trough it again the running time for finding the independent set would be more than O(n)? Thank you for helping me out here, I'm really appreciating this.

Algific 2009-10-14 20:46:11

No. It won't be. You'll be visiting **at most** `n` nodes in the second pass. It'll be O(n).

Mehrdad Afshari 2009-10-14 20:50:29

Mehrdad I need one last thing from you. http://stackoverflow.com/questions/1571547/java-need-help-implementing-an-algorithm I got the algorithm working. Now I need to point out in my code were I would mark my nodes as chosen?

Algific 2009-10-15 11:08:01

Answer 2

A:

I would take-and-remove all leaves first while marking their parents as not-to-take, then remove all leaves that are marked until no such leaves are left, then recurse until the tree is empty. I don't have a proof that this always produces the largest possible set, but I believe it should.

Svante 2009-10-14 17:01:12

Ah, you kinda go every other height level from the bottom towards the root? Not bad! I'll implement it and see.

Algific 2009-10-14 17:09:59

The leaves do not need to be at the same level.

Svante 2009-10-15 07:20:20

ansaurus

tags:

views:

answers:

Java Algorithm for finding the largest set of independent nodes in a binary tree

related questions