int hasPathSum(struct node* node, int sum) {
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Wed, Jan 5, 2011 at 12:21 PM, ADITYA KUMAR <aditya...@gmail.com> wrote:
> problem has many properties like its a BST with parent pointer
> we shud think of such a solution which uses its both property
>
> If we will think abt the brute force recursive solution
> its complexity will be O(no_of_nodes*height)
>
> which can be made more efficient by putting some restrictions
> in each recursion
> sum "s"
> remaining sum "rs"
> if node.value > rs/2 then search in left subtree for rs-node.value and s
> if node.value < rs/2 then search in both subtree for rs-node.value and s
> stop recursion if rs-node.value ==0 or node.value=s
>
>
>
> On Sun, Dec 26, 2010 at 10:38 PM, MAC <macatad...@gmail.com> wrote:
>
>> you are given a bst where each node has a int value , parent pointer , and
>> left and right pointers , write a function to find a path with a given sum
>> value. Path can go from left subtree tree , include root and go to right
>> tree as well . we need to find these paths also .
>>
>>
>> 5
>> 1 10
>> 0 2 6 11
>>
>> so to find 16 we say it is 1 to 5 to 10
>>
>> --
>> thanks
>> --mac
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards
> Aditya Kumar
> B-tech 3rd year
> Computer Science & Engg.
> MNNIT, Allahabad.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
