Given a binary tree and an integer K. Find the number of paths in the tree which have their sum equal to K.
A path may start from any node and end at any node in the downward direction.
Example 1:
Input:      
Tree = 
          1                               
        /   \                          
       2     3
K = 3
Output: 2
Explanation:
Path 1 : 1 + 2 = 3
Path 2 : only leaf node 3
Example 2:
Input: 
Tree = 
           1
        /     \
      3        -1
    /   \     /   \
   2     1   4     5                        
        /   / \     \                    
       1   1   2     6    
K = 5                    
Output: 8
Explanation:
The following paths sum to K.  
3 2 
3 1 1 
1 3 1 
4 1 
1 -1 4 1 
-1 4 2 
5 
1 -1 5 
Your Task:  
You don't need to read input or print anything. Complete the function sumK() which takes root node and integer K as input parameters and returns the number of paths that have sum K. Since the answer may be very large, compute it modulo 10^{9}+7.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of Tree)
Constraints:
1 ≤ N ≤ 10^{5}
-10^{5} ≤ Node Value ≤ 10^{5}
-10^{9} ≤ k ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''

class Solution:

    def sumK(self,root,k):

        # code here

Solutions:
class Solution:

	def __init__(self):
		self.count = 0

	def sumpath(self, root, k, sum, d):
		if root == None:
			return
		sum += root.data
		if sum == k:
			self.count += 1
		if sum - k in d:
			self.count += d[sum - k]
		if sum in d:
			d[sum] += 1
		else:
			d[sum] = 1
		self.sumpath(root.left, k, sum, d)
		self.sumpath(root.right, k, sum, d)
		d[sum] -= 1

	def sumK(self, root, k):
		d = dict()
		sum = 0
		self.sumpath(root, k, sum, d)
		return self.count


class Solution:

	def solve(self, root, k, path, cnt):
		if root is None:
			return
		path.append(root.data)
		self.solve(root.left, k, path, cnt)
		self.solve(root.right, k, path, cnt)
		n = len(path)
		total = 0
		for i in range(n - 1, -1, -1):
			total += path[i]
			if total == k:
				cnt[0] += 1
		path.pop()

	def solve(self, root, k, summ, data, cnt):
		if root is None:
			return
		summ += root.data
		cnt[0] += data.get(summ - k, 0)
		data[summ] = data.get(summ, 0) + 1
		self.solve(root.left, k, summ, data, cnt)
		self.solve(root.right, k, summ, data, cnt)
		data[summ] -= 1

	def sumK(self, root, k):
		cnt = [0]
		path = []
		data = {0: 1}
		self.solve(root, k, 0, data, cnt)
		return cnt[0]


class Solution:

	def solve(self, root, k, su, d):
		if root == None:
			return
		su += root.data
		self.count += d.get(su - k, 0)
		d[su] = d.get(su, 0) + 1
		self.solve(root.left, k, su, d)
		self.solve(root.right, k, su, d)
		d[su] -= 1

	def sumK(self, root, k):
		self.count = 0
		su = 0
		d = {0: 1}
		self.solve(root, k, su, d)
		return self.count


class Solution:

	def util(self, root, k, sm, mp):
		if not root:
			return
		sm += root.data
		self.paths += mp.get(sm - k, 0)
		if sm == k:
			self.paths += 1
		mp[sm] = mp.get(sm, 0) + 1
		self.util(root.left, k, sm, mp)
		self.util(root.right, k, sm, mp)
		mp[sm] = mp.get(sm, 0) - 1

	def sumK(self, root, k):
		self.paths = 0
		self.util(root, k, 0, {})
		return self.paths