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

## No comments:

## Post a Comment