Find number of paths whose sum is equal to K in a Binary Tree

Problem: You are given a binary tree in which each node contains an integer value positive or negative. Find the number of paths that sum to a given value K. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Example:

K = 3

      1
     /  \
    2   -3
   / \    \
  7  -3    5
       \
        4

Return 3. The paths that sum to 3 are:

1 -> 2
2 -> -3 -> 4
1 -> -3 -> 5

Approach: We can solve it using Pre-Order traversal with hashing. Just look at the implementation to understand the approach. It's fairly straight forward.

 

Implementation in C#:

        public int PathSum(TreeNode root, int targetSum)

    {

        if (root == null)

        {

            return 0;

        }

        var sumMap = new Dictionary<long, int>();

        sumMap[0] = 1;

        return this.FindNumOfPaths(root, targetSum, 0, sumMap);

    }

    private int FindNumOfPaths(TreeNode node,

                               int targetSum,

                               long currSum,

                               Dictionary<long, int> sumMap)

    {

        if (node == null)

        {

            return 0;

        }

        currSum += node.val;

        int numOfPaths = 0;

        if (sumMap.ContainsKey(currSum - targetSum))

        {

            numOfPaths += sumMap[currSum - targetSum];

        }

        if (!sumMap.ContainsKey(currSum))

        {

            sumMap[currSum] = 0;

        }

        ++sumMap[currSum];

        numOfPaths += this.FindNumOfPaths(node.left,

                                         targetSum,

                                         currSum,

                                         sumMap) +

                      this.FindNumOfPaths(node.right,

                                         targetSum,

                                          currSum,

                                          sumMap);

        // This node is no more in the path

        --sumMap[currSum];

        if (sumMap[currSum] == 0)

        {

            sumMap.Remove(currSum);

        }

        return numOfPaths;

    }

Complexity: O(n)