Author |
Topic: root to leaf sum with given numbers (Read 1130 times) |
|
srikanth.iiita
Newbie
Posts: 33
|
 |
root to leaf sum with given numbers
« on: Mar 13th, 2010, 11:46am » |
 Quote  Modify
|
given a bst,a number s and a group of numbers g, check whether all the elements of g occur in the same path,all elements sum upto s without including root and the leaf
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7528
|
|
Re: root to leaf sum with given numbers
« Reply #1 on: Mar 15th, 2010, 9:06am » |
Quote Modify
|
When you say "all elements sum up to s", does it refer to all elements in the BST or all elements in a path containing all elements of G?
And by path, do you mean a path starting from the root, or any path linking 2 nodes?
|
|
IP Logged |
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: root to leaf sum with given numbers
« Reply #2 on: Mar 16th, 2010, 10:41am » |
Quote Modify
|
sum of elements means (sum of given numbers in group g)
we have to find a root-leaf path ( excluding root,leaf)..
all other numbers should be equal to respective numbers in g
|
|
IP Logged |
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: root to leaf sum with given numbers
« Reply #3 on: Mar 16th, 2010, 10:45am » |
Quote Modify
|
the elements of g should lie on a single path.. from root to leaf
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: root to leaf sum with given numbers
« Reply #4 on: Mar 16th, 2010, 11:03am » |
Quote Modify
|
Do we need to find all the elements of g on the path?
And wouldn't that mean we can check before hand whether they sum to s?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: root to leaf sum with given numbers
« Reply #5 on: Mar 16th, 2010, 11:18am » |
Quote Modify
|
we have to find all the elements of g on a single path...
i don't know what to do with the sum...
|
| « Last Edit: Mar 16th, 2010, 11:19am by srikanth.iiita » |
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: root to leaf sum with given numbers
« Reply #6 on: Mar 17th, 2010, 10:25pm » |
Quote Modify
|
I got it all wrong.. Does the sum refers to the sum of all the elements on the path.
|
|
IP Logged |
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: root to leaf sum with given numbers
« Reply #7 on: Mar 18th, 2010, 3:25am » |
Quote Modify
|
sum of numbers in g.. i think....
|
|
IP Logged |
|
|
|
sushiljacksparrow
Newbie
Posts: 1
|
|
Re: root to leaf sum with given numbers
« Reply #8 on: Mar 24th, 2010, 9:08pm » |
Quote Modify
|
the recursive version of the code should look something like this..
bool check( bool flag, set <int>s, int sum, node *root)
{
if(root->next->next ==NULL && sum==0 && set.size()==0)
return true;
if(root->next->next==NULL)
return false;
if(flag)
{
return check(!flag, s, sum, root->left) || check(!flag,s,sum,root->right);
}
else
{
return (s.find(root->data)!=s.end())?( (flag,s.delete(root->data),sum-root->data,root->left )||(flag,s.delete(root->data),sum-root->data,root->right)) : false;
}
}
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print