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

Post a Comment

0 Comments

Close Menu