Author |
Topic: Tree (Read 834 times) |
|
witee
Newbie
Posts: 48
|
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?
|
|
 IP Logged |
|
|
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Re: Tree
« Reply #1 on: Jul 28th, 2010, 8:09pm » |
 Quote  Modify
|
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.
|
|
IP Logged |
|
|
|
nakli
Junior Member
Gender:
Posts: 62
|
|
Re: Tree
« Reply #2 on: Jul 28th, 2010, 9:29pm » |
Quote Modify
|
on Jul 28th, 2010, 8:09pm, 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)
}
|
|
IP Logged |
I was born naked on a bed with a lady.
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Tree
« Reply #3 on: Jul 28th, 2010, 10:26pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Tree
« Reply #4 on: Jul 29th, 2010, 2:19am » |
Quote Modify
|
on Jul 28th, 2010, 10:26pm, 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]
|
| « Last Edit: Jul 29th, 2010, 4:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Tree
« Reply #5 on: Jul 29th, 2010, 3:21am » |
Quote Modify
|
Thanks Tower. I got it.
Just small correction, in for loop you have mentioned, in += a; but it should be in += b;
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Tree
« Reply #6 on: Jul 29th, 2010, 4:47am » |
Quote Modify
|
on Jul 29th, 2010, 3:21am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print