# Given a binary tree, find path sum

Given a tree and a sum returns true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.let’s consider the following binary tree as an example, and the path sum value is 9.

4

/ \

2 5

/ \

1 3

Root-to-leaf paths:

path 1: 4 2 1

path 2: 4 2 3

path 3: 4 5

You can see that there are two path that gives sum 9 (Path2 and Path 3).Traverse the tree from root to leaves in top down fashion and subtract the node value from the sum and check to see if the sum is 0 when you run out of tree.

public bool HasPathSum(int sum)
{
return HasPathSum(_root, sum);
}
private bool HasPathSum(Node root, int sum)
{
// return true if we run out of tree and sum==0
if (root ==  null)
return sum == 0;
else
{
int subSum = sum - root.Data;
return (
HasPathSum(root.Left, subSum)
|| HasPathSum(root.Right, subSum)
);
}

}


Reactions