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.