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 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