Question: Find if any branch of a tree has sum equal to given value. Branch may or may not start from root.
Also print the branch segment, which adds to given value.
Ex: For below tree, if given value is:
16 : Answer is TRUE
17 : Answer is TRUE
12 : Answer is FALSE
Assumption: Tree has only positive integers as node values.
Algorithm: We have to do Length-First-Search and keep subtracting the node’s value from given value (Sum to be achieved). If we reach the leaf node and remaining sum is not zero, return false for that particular branch. Else if remaining sum is zero, print branch and return true.
Above solution works fine if we talk about branches starting from root. For all branch segments, keep the running branch in an array. Maintain 2 pointers denoting start and end of branch segment. If remaining sum becomes less than zero, before reaching leaf node, add array[start] in the sum and increment start by 1 until remaining sum is less than 0. Other than this everything is same as above.
Code:
bool lfs(treenode* node, int sum, int arr[], int start, int end)
{
int i;
if(!node && sum!=0){
return false;
}
arr[end] = node->val;
sum = sum - arr[end];
end++;
while(sum < 0){
sum = sum + arr[start];
start++;
}
if (sum == 0){
for (i=start; i< end; i++)
cout << arr[i] << " ";
cout << endl;
return true;
}
return (lfs(node->left, sum, arr, start, end) || lfs(node->right, sum, arr, start, end));
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
hey can give brief info , what happen if node start from left subtree & goes to right subtree that gives us desired sum isn't it ? then i hope your solution won't work ??
@Anonymous: As per question statement, sum is only for a branch in the tree, not in a combination of branches.
@Akash what the time complexity of solution ?? O(N) ??
@Anonymous: Since we are visiting every node just once, worst case time complexity is O(n).
An easier solution to understand is to look at every node as the end of the branch, not the beginning. In this way, you can start from every node and work your way up to the root adding the values of what you see. This solution is O(n * h), though (where h is the height of the tree - defined as the maximum distance over all nodes from the root). But it has a good advantage of easy coding and ignoring your assumption of positive values (it works for any value actually). Note that it's not enough to stop before reaching the root because you have negative values now, otherwise you could miss some paths. For example, imagine - from a given node - the path up encounters (1, 2, 3, 6, -12, 24, 3) and you're seeking 12. Though you may stop at 6 (1 + 2 + 3 + 6 = 12), but you'll miss the branch (1, 2, 3, 6, -12, 24), which can only be realized at this point. Note that the branch (-12, 24) is realized during processing another node, so we don't care about it now.
Maybe you can think more of optimizing this... please share your opinion.
Thank you so much for your post; it has provided us with an excellent idea.