My approach :
int FindPath(Node n , sum s )
{
FindPath(n->left , s ) ||
FindPath(n->right , s) ||
OneOf { a1 = AllSumsFromLeafToRoot( n->left ) } + n->value +
Oneof { a2 = AllSumsFromLeafToRoot( n->right ) == s ) }
// Use a1 and a2 to find out the actual path
}
Here all possible sums from a node to the leaves can be precomputed in O(n)
(one inorder traversal) and so lookup can be made in O(1).
For each node store < child_left , <sum1,sum2,sum3 ...> > , < child_right
,< sum1,sum2,sum3 ...> > We may need this data to traverse the tree again
with the sum values to find the path.
Looks complicated to me too, waiting for comments.
On Thu, Jun 30, 2011 at 4:17 PM, sagar pareek <[email protected]> wrote:
> Try traversing in LEVEL order and maintain array for each level...(Levels
> can be found by height of tree)
> then try by calculating sums starting from root(level zero) to higher
> level.
> Its typical to explain here but i found it as a solution and that will
> definitely found the solution.
>
> On Thu, Jun 30, 2011 at 9:08 AM, rajeev bharshetty
> <[email protected]>wrote:
>
>> By traversing tree either preorder or inorder or postorder and storing the
>> partial sums along the way and comparing the partial sums with the required
>> sum can solve the problem
>>
>>
>> On Wed, Jun 29, 2011 at 7:56 PM, Akshata Sharma <
>> [email protected]> wrote:
>>
>>> How to find a path in a given binary tree which sums up to a given target
>>> value?
>>> for example if the given BT is
>>>
>>> 5
>>> / \
>>> 3 2
>>> /
>>> 7
>>> and if the target is 10, then the path is ---- root(5) + left node(3) +
>>> right node (2).
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
regards,
chinna.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
