wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Tree
        
(Message started by: witee on Jul 28^th, 2010, 4:06pm)

Title: Tree
Post by witee on Jul 28^th, 2010, 4:06pm

A binary tree is given with a positive weight attached to each node. Find the subset of nodes in the tree whose sum give you the maximum weight such that if a node is in the subset, none of its children can be in that subset.
Pseudo code plz?

Title: Re: Tree
Post by sateesp on Jul 28^th, 2010, 8:09pm

Here we will get only two sets...
Set1= {root,secondlevel nodes, fourth level nodes....}
set2 = {first levl nodes, thrid level nodes...}

Do the level order traversal and find the sum of set1 elements and sum of set2 elements. Return whichever is the maximum.

Title: Re: Tree
Post by nakli on Jul 28^th, 2010, 9:29pm

on 07/28/10 at 20:09:34, sateesp wrote:

Here we will get only two sets...

There are more than two sets possible. Let a node at fourth level and first level have a very heavy weight. Then in my subset i would include both of them, skipping the node at second and third level.

This seems like a dynamic programming problem.

Pseudo code:
maximumweight current node
{
If (weight of current node) heavier than (sum of maximumweight of its children)
return (weight of current node)
else return (sum of maximumweight of its children)
}

Title: Re: Tree
Post by sateesp on Jul 28^th, 2010, 10:26pm

In given problem, it has been mentioned that,
A binary tree is given with a positive weight attached to each node.

If you skip any node, then it's not maximum subset.

Title: Re: Tree
Post by towr on Jul 29^th, 2010, 2:19am

on 07/28/10 at 22:26:33, sateesp wrote:

If you skip any node, then it's not maximum subset.

You may want to skip a level in a particular subtree.
for example if you have
1
2 20
10 3 4 5
neither 2+20, nor 1+10+3+4+5 are maximum. The maximum is 20+10+3

You should do this recursively, returning a pair of values for each node, the weight when you do and do not include it. If you don't include the current node, you take the sum of the maximum of all pairs of all children, if you do include it, you take the sum of the total weights of child subtrees excluding the immediate children.
That gives you in O(n) time what you want.

Pseudo
Code:

foo(root)
{
if (!root)
return [0,0];
else
{
in=root->val;
ex=0;
foreach child of root
{
[a,b] = foo(child);
in += b;
ex += max(a,b);
}
return [in, ex];
}
}

[edit]Fixed mistake pointed out below[/edit]

Title: Re: Tree
Post by sateesp on Jul 29^th, 2010, 3:21am

Thanks Tower. I got it.

Just small correction, in for loop you have mentioned, in += a; but it should be in += b;

Title: Re: Tree
Post by towr on Jul 29^th, 2010, 4:47am

on 07/29/10 at 03:21:22, sateesp wrote:

Just small correction, in for loop you have mentioned, in += a; but it should be in += b;

Ah, yes; thank you. I'll correct that.