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)
);
}
}