Binary Tree Path Sums Divisible by K

[hamidgasmi]

You are given a binary tree in which each node contains an integer value.

Find the number of paths which sum is divisible by 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:

root = [10,5,-3,2,2,null,18,3,-2,null,1], sum = 5

      10
     /  \
    5   -3
   / \    \
  2   2   18
 / \   \
3  -2   1

Return 10. The paths which sum is divisible by 5 are:

1. 10
2. 5
3. 10 -> 5
4. 2 -> 3
5. 5 -> 2 -> 3
6. 10 -> 5 -> 2 -> 3
7. 2 -> -2
8. 5 -> 2 -> -2
9. 10 -> 5 -> 2 -> -2
10. 10 -> -3 -> 18