Given a binary tree and an integer X. Your task is to complete the function countSubtreesWithSumX() that returns the count of the number of subtress having total node’s data sum equal to the value X.
Example: For the tree given below:             
              5
            /    \
        -10     3
        /    \    /  \
      9     8  -4 7
Subtree with sum 7:
             -10
            /      \
          9        8
and one node 7.
Example 1:
Input:
       5
    /    \
  -10     3
 /   \   /  \
 9   8 -4    7
X = 7
Output: 2
Explanation: Subtrees with sum 7 are
[9, 8, -10] and [7] (refer the example
in the problem description).
Example 2:
Input:
    1
  /  \
 2    3
X = 5
Output: 0
Explanation: No subtree has sum equal
to 5.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countSubtreesWithSumX() which takes the root node and an integer X as inputs and returns the number of subtrees of the given Binary Tree having sum exactly equal to X.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= N <= 10^{3}
-10^{3} <= Node Value <= 10^{3}
 
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).

Starter code:
#User function Template for python3



'''
# Node Class:
class Node:
    def __init__(self,val):
        self.data = val
        self.left = None
        self.right = None
'''

#Function to count number of subtrees having sum equal to given sum.
def countSubtreesWithSumX(root, x):
    
    # code here

Solutions:
def countSubtreesWithSumX1(root, x):
	global count
	if root == None:
		return 0
	l = countSubtreesWithSumX1(root.left, x)
	r = countSubtreesWithSumX1(root.right, x)
	if l + r + root.data == x:
		count += 1
	return l + r + root.data

def countSubtreesWithSumX(root, x):
	global count
	count = 0
	countSubtreesWithSumX1(root, x)
	return count


def countSubtreesWithSumX(root, x):

	def solve(root, x, c):
		if not root:
			return 0
		sum = root.data + solve(root.left, x, c) + solve(root.right, x, c)
		if sum == x:
			c[0] += 1
		return sum
	c = [0]
	solve(root, x, c)
	return c[0]


def countSubtreesWithSumX(root, x):
	count = 0

	def helper(root):
		nonlocal count
		if root:
			x1 = helper(root.left)
			x2 = helper(root.right)
			if x1 + x2 + root.data == x:
				count += 1
			return x1 + x2 + root.data
		return 0
	helper(root)
	return count


def countsubtree(root, count, x):
	if root == None:
		return 0
	left = countsubtree(root.left, count, x)
	right = countsubtree(root.right, count, x)
	sum = 0
	sum = left + right + root.data
	if sum == x:
		count[0] += 1
	return sum

def countSubtreesWithSumX(root, x):
	count = [0]
	countsubtree(root, count, x)
	return count[0]


def countSubtreesWithSumX(root, x):
	m = {}

	def fun(root):
		if root == None:
			return 0
		s = 0
		s += root.data
		s += fun(root.left)
		s += fun(root.right)
		if s not in m:
			m[s] = 1
		else:
			m[s] += 1
		return s
	fun(root)
	if x in m:
		return m[x]
	else:
		return 0


def solve(root, x):
	global count
	if root == None:
		return 0
	left = solve(root.left, x)
	right = solve(root.right, x)
	if left + right + root.data == x:
		count += 1
	return left + right + root.data

def countSubtreesWithSumX(root, x):
	global count
	count = 0
	k = solve(root, x)
	return count


def util(root, x):
	if root == None:
		return [0, 0]
	l = util(root.left, x)
	r = util(root.right, x)
	if l[0] + r[0] + root.data == x:
		return [x, l[1] + r[1] + 1]
	else:
		return [l[0] + r[0] + root.data, l[1] + r[1]]

def countSubtreesWithSumX(root, x):
	ans = util(root, x)
	return ans[1]


def util(root, x):
	if root is None:
		return 0
	ls = util(root.left, x)
	rs = util(root.right, x)
	sum = ls + rs + root.data
	if sum == x:
		util.count += 1
	return sum

def countSubtreesWithSumX(root, x):
	if root is None:
		return 0
	util.count = 0
	ls = util(root.left, x)
	rs = util(root.right, x)
	sum_of_current = ls + rs + root.data
	if sum_of_current == x:
		util.count += 1
	return util.count


class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

def countSubtreesWithSumX(root, x):
	stack = [root]
	parent = {}
	parent[root] = Node(0)
	vis = set()
	while stack:
		top = stack[-1]
		if top.left and top.left not in vis:
			vis.add(top.left)
			stack.append(top.left)
			parent[top.left] = top
		elif top.right and top.right not in vis:
			stack.append(top.right)
			vis.add(top.right)
			parent[top.right] = top
		else:
			pop = stack.pop()
			parent[top].data = parent[top].data + top.data
	stack = [root]
	res = 0
	while stack:
		top = stack.pop()
		if top.data == x:
			res += 1
		if top.left:
			stack.append(top.left)
		if top.right:
			stack.append(top.right)
	return res


ans = 0

def solve(node, x):
	if not node:
		return 0
	global ans
	temp = solve(node.left, x) + solve(node.right, x) + node.data
	if temp == x:
		ans += 1
	return temp

def countSubtreesWithSumX(root, x):
	global ans
	ans = 0
	solve(root, x)
	return ans


count = 0

def countSubtreesWithSumX(root, x):
	global count
	count = 0
	_countSubtreesWithSumX(root, x)
	return count

def _countSubtreesWithSumX(root, x):
	if root == None:
		return 0
	global count
	lh = _countSubtreesWithSumX(root.left, x)
	rh = _countSubtreesWithSumX(root.right, x)
	if lh + rh + root.data == x:
		count += 1
	return lh + rh + root.data


def countSubtreesWithSumX(root, x):
	count = [0]

	def solver(root, x):
		if not root:
			return 0
		left = solver(root.left, x)
		right = solver(root.right, x)
		if left + right + root.data == x:
			count[0] += 1
		return left + right + root.data
	store = solver(root, x)
	return count[0]


def countSubtreesWithSumX(root, x):

	def func(root, x, res):
		if root is None:
			return 0
		left = func(root.left, x, res)
		right = func(root.right, x, res)
		ans = root.data + left + right
		if ans == x:
			res[0] += 1
		return ans
	res = [0]
	func(root, x, res)
	return res[0]


def countSubtreesWithSumX(root, x):
	res = 0

	def dfs(root, x):
		nonlocal res
		if root == None:
			return 0
		left = dfs(root.left, x)
		right = dfs(root.right, x)
		cur_sum = left + right + root.data
		if cur_sum == x:
			res += 1
		return left + right + root.data
	dfs(root, x)
	return res


def Postorder(root, x, count):
	if root == None:
		return 0
	l = Postorder(root.left, x, count)
	r = Postorder(root.right, x, count)
	sum = l + r + root.data
	if sum == x:
		count[0] += 1
	return sum

def countSubtreesWithSumX(root, x):
	count = [0]
	Postorder(root, x, count)
	return count[0]


def countSubtreesWithSumX(root, x):
	l = [0]

	def f(t):
		if t == None:
			return 0
		p = t.data + f(t.left) + f(t.right)
		if p == x:
			l[0] += 1
			return x
		else:
			return p
	f(root)
	return l[0]


def helper(root, x, count):
	if root is None:
		return 0
	sum1 = helper(root.left, x, count) + root.data + helper(root.right, x, count)
	if sum1 == x:
		count[0] += 1
	return sum1

def countSubtreesWithSumX(root, x):
	count = [0]
	helper(root, x, count)
	return count[0]


def preorder(root, target, res):
	if root is None:
		return 0
	left_sum = preorder(root.left, target, res)
	right_sum = preorder(root.right, target, res)
	if left_sum + right_sum + root.data == target:
		res[0] += 1
	return left_sum + right_sum + root.data

def countSubtreesWithSumX(root, x):
	res = [0]
	preorder(root, x, res)
	return res[0]


def countSubtreesWithSumX(root, x):
	(res, _) = countSubtreesUtil(root, x)
	return res

def countSubtreesUtil(root, x):
	if not root:
		return (0, 0)
	(num_left, sum_left) = countSubtreesUtil(root.left, x)
	(num_right, sum_right) = countSubtreesUtil(root.right, x)
	sum = root.data + sum_left + sum_right
	num = num_left + num_right
	if sum == x:
		num += 1
	return (num, sum)


def countSubtreesWithSumX(root, x):
	return helper(root, x)[1]

def helper(root, target):
	if root is None:
		return (0, 0)
	(sum_left, count_left) = helper(root.left, target)
	(sum_right, count_right) = helper(root.right, target)
	summa = sum_left + sum_right + root.data
	count = (summa == target) + count_left + count_right
	return (summa, count)


def util(root, x, ans):
	if not root:
		return 0
	sm = 0
	sm += root.data
	sm += util(root.left, x, ans)
	sm += util(root.right, x, ans)
	if sm == x:
		ans[0] += 1
	return sm

def countSubtreesWithSumX(root, x):
	ans = [0]
	util(root, x, ans)
	return ans[0]


def countSubtreesWithSumX(root, x):
	count = [0]
	ans(root, x, count)
	return count[0]

def ans(root, x, count):
	if root == None:
		return 0
	a = ans(root.left, x, count)
	b = ans(root.right, x, count)
	sum = a + b + root.data
	if sum == x:
		count[0] = count[0] + 1
	return sum


class Solution:

	def __init__(self):
		self.c = 0

	def check(self, a, k):
		if a == None:
			return 0
		o = self.check(a.left, k)
		p = self.check(a.right, k)
		q = a.data + o + p
		if q == k:
			self.c += 1
		return q

def countSubtreesWithSumX(root, x):
	o = Solution()
	o.check(root, x)
	return o.c


def countSubtreesWithSumX(root, x):
	val = [0]

	def Sum(root, x, val):
		if root == None:
			return 0
		s = Sum(root.left, x, val) + Sum(root.right, x, val) + root.data
		if x == s:
			val[0] += 1
		return s
	Sum(root, x, val)
	return val[0]


from collections import defaultdict

def countSubtreesWithSumX(root, x):
	if not root:
		return []
	mp = defaultdict(int)
	res = []

	def getsum(root):
		if not root:
			return 0
		s = getsum(root.left) + root.data + getsum(root.right)
		if s == x:
			mp[s] += 1
		return s
	getsum(root)
	return mp[x]


def travell(root, x, dp):
	if root == None:
		return 0
	currSum = root.data + travell(root.left, x, dp) + travell(root.right, x, dp)
	if currSum == x:
		dp[0] += 1
	return currSum

def countSubtreesWithSumX(root, x):
	dp = [0]
	travell(root, x, dp)
	return dp[0]


def countSubtreesWithSumX(root, x):

	def traversal(root):
		nonlocal count
		if root == None:
			return 0
		ls = traversal(root.left)
		rs = traversal(root.right)
		sum1 = ls + rs + root.data
		if sum1 == x:
			count += 1
		return sum1
	count = 0
	traversal(root)
	return count


count = 0

def countSubtreesWithSumX(root, x):
	C = [0]
	dfs(root, x, C)
	return C[0]

def dfs(root, x, C):
	global count
	if root:
		a = dfs(root.left, x, C)
		b = dfs(root.right, x, C)
		Sum = a + b + root.data
		if Sum == x:
			C[0] += 1
		return Sum
	return 0


def countSubtreesWithSumX(root, x):
	if root is None:
		return 0
	count = [0]
	ls = sumTree(root.left, count, x)
	rs = sumTree(root.right, count, x)
	if ls + rs + root.data == x:
		count[0] += 1
	return count[0]

def sumTree(root, count, x):
	if root is None:
		return 0
	ls = sumTree(root.left, count, x)
	rs = sumTree(root.right, count, x)
	s = ls + rs + root.data
	if s == x:
		count[0] += 1
	return s


def countSubtreesWithSumX(root, x):
	res = [0]
	rec(root, x, res)
	return res[0]

def rec(root, x, res):
	if root is None:
		return 0
	sumi = root.data
	sumi += rec(root.left, x, res)
	sumi += rec(root.right, x, res)
	if sumi == x:
		res[0] += 1
	return sumi


def countSubtreesWithSumX(root, x):
	count = 0

	def dfs(root):
		nonlocal count
		if not root:
			return 0
		l = dfs(root.left)
		r = dfs(root.right)
		s = root.data + l + r
		if s == x:
			count += 1
		return s
	dfs(root)
	return count


def calc(curr, d):
	if curr == None:
		return 0
	sl = calc(curr.left, d)
	sr = calc(curr.right, d)
	d[curr] = sl + sr + curr.data
	return d[curr]

def countSubtreesWithSumX(root, x):
	d = {}
	calc(root, d)
	c = 0
	va = d.values()
	for v in va:
		if v == x:
			c += 1
	return c


class sol:
	c = 0

	def solve(self, root, x):
		if root == None:
			return 0
		else:
			a = self.solve(root.left, x)
			b = self.solve(root.right, x)
			curr = a + b + root.data
			if curr == x:
				self.c += 1
			return root.data + a + b

def countSubtreesWithSumX(root, x):
	a = sol()
	a.solve(root, x)
	return a.c


def countSubtreesWithSumX(root, x):

	def solve(root, x, count):
		if root is None:
			return 0
		summ = solve(root.left, x, count) + root.data + solve(root.right, x, count)
		if summ == x:
			count[0] += 1
		return summ
	count = [0]
	solve(root, x, count)
	return count[0]


def modify(root, x, count):
	sum = lsum = rsum = 0
	if root.left:
		lsum = modify(root.left, x, count)
	if root.right:
		rsum = modify(root.right, x, count)
	sum = lsum + rsum + root.data
	if sum == x:
		count[0] += 1
	return sum

def countSubtreesWithSumX(root, x):
	res = [0]
	a = modify(root, x, res)
	return res[0]


def countSubtreesWithSumX(root, x):
	ans = [0]
	dfs(root, x, ans)
	return ans[0]

def dfs(n, x, ans):
	if not n:
		return 0
	l = dfs(n.left, x, ans)
	r = dfs(n.right, x, ans)
	s = l + r + n.data
	if s == x:
		ans[0] += 1
	return s


def countSubtreesWithSumX(root, x):
	if not root:
		return 0
	if not root.left and (not root.right):
		if root.data == x:
			return 1
	res = [0]
	_ = subtreeSum(root, x, res)
	return res[0]

def subtreeSum(root, x, res):
	if not root:
		return 0
	l_subtree = subtreeSum(root.left, x, res)
	r_subtree = subtreeSum(root.right, x, res)
	subtreeSummation = l_subtree + r_subtree + root.data
	if subtreeSummation == x:
		res[0] += 1
	return subtreeSummation


def count(root, x):
	if root is None:
		return [0, 0]
	(l, r) = (count(root.left, x), count(root.right, x))
	if root.data + l[0] + r[0] == x:
		return [root.data + l[0] + r[0], 1 + l[1] + r[1]]
	else:
		return [root.data + l[0] + r[0], l[1] + r[1]]

def countSubtreesWithSumX(root, x):
	return count(root, x)[1]


def recursive(root, X, ans):
	if root is None:
		return 0
	data = root.data + recursive(root.left, X, ans) + recursive(root.right, X, ans)
	if data == X:
		ans[0] += 1
	return data

def countSubtreesWithSumX(root, x):
	ans = [0]
	sum_val = recursive(root, x, ans)
	return ans[0]


def countSubtreesWithSumX(root, x):
	count = [0]

	def dfs(root, x, count):
		if root is None:
			return 0
		l = dfs(root.left, x, count)
		r = dfs(root.right, x, count)
		t = l + r + root.data
		if t == x:
			count[0] += 1
		return t
	dfs(root, x, count)
	return count[0]


def countSubtreesWithSumX(root, x):

	def checkSubtree(root, x, cnt):
		if not root:
			return (0, cnt)
		(suml, cnt) = checkSubtree(root.left, x, cnt)
		(sumr, cnt) = checkSubtree(root.right, x, cnt)
		sum = root.data + suml + sumr
		if sum == x:
			cnt += 1
		return (sum, cnt)
	return checkSubtree(root, x, 0)[1]


def countSubtreesWithSumX(root, x):
	count = [0]
	countSubtreesWithSumXUtil(root, x, count)
	return count[0]

def countSubtreesWithSumXUtil(root, x, count):
	if not root:
		return 0
	c = root.data + countSubtreesWithSumXUtil(root.left, x, count) + countSubtreesWithSumXUtil(root.right, x, count)
	if c == x:
		count[0] += 1
	return c


def countSubtreesWithSumX(root, x):
	res = []

	def find(root, x, res):
		if not root:
			return 0
		left = find(root.left, x, res)
		right = find(root.right, x, res)
		curr = root.data + left + right
		if curr == x:
			res.append(root.data)
		return curr
	find(root, x, res)
	return len(res)


def solve(root, x, count):
	if root == None:
		return (0, count)
	(ls, count) = solve(root.left, x, count)
	(rs, count) = solve(root.right, x, count)
	summ = ls + rs + root.data
	if summ == x:
		count += 1
	return (summ, count)

def countSubtreesWithSumX(root, x):
	return solve(root, x, 0)[-1]


def countSubtreesWithSumX(root, x):
	subTrees = [0]

	def getSum(root):
		if not root:
			return 0
		ls = getSum(root.left)
		rs = getSum(root.right)
		if ls + rs + root.data == x:
			subTrees[0] += 1
		return root.data + ls + rs
	getSum(root)
	return subTrees[0]


def countSubtreesWithSumX(root, x):
	count = 0

	def solve(root, x):
		nonlocal count
		if root == None:
			return 0
		l = solve(root.left, x)
		r = solve(root.right, x)
		if l + r + root.data == x:
			count = count + 1
		return l + r + root.data
	solve(root, x)
	return count


def countSubtreesWithSumX(root, x):

	def solve(root, x, dp):
		if root == None:
			return 0
		left = solve(root.left, x, dp)
		right = solve(root.right, x, dp)
		if root.data + left + right == x:
			dp[0] += 1
		return root.data + left + right
	dp = [0]
	solve(root, x, dp)
	return dp[0]


def countSubtreesWithSumX(root, x):
	if root == None:
		return 0

	def count_subtree(root, x, result):
		if root == None:
			return 0
		leftSum = count_subtree(root.left, x, result)
		rightSum = count_subtree(root.right, x, result)
		if leftSum + rightSum + root.data == x:
			result[0] += 1
		return leftSum + rightSum + root.data
	result = [0]
	count_subtree(root, x, result)
	return result[0]


def traverseTree(root, x):
	if root is None:
		return 0
	left = traverseTree(root.left, x)
	right = traverseTree(root.right, x)
	sum_subtree = left + right + root.data
	if sum_subtree == x:
		traverseTree.count += 1
	return sum_subtree

def countSubtreesWithSumX(root, x):
	arr = [0]
	traverseTree.count = 0
	traverseTree(root, x)
	return traverseTree.count


def countSubtreesWithSumX(root, x):
	ans = [0]

	def rec(nod, x, sumi):
		if nod is None:
			return 0
		lh = rec(nod.left, x, sumi)
		rh = rec(nod.right, x, sumi)
		p = nod.data + lh + rh
		if p == x:
			ans[0] += 1
		return p
	rec(root, x, 0)
	return ans[0]


def countSubtreesWithSumX(root, x):
	count = [0]
	if root == None:
		return

	def subtreecount(root, sum):
		if root == None:
			return 0
		l = subtreecount(root.left, sum)
		r = subtreecount(root.right, sum)
		s = l + r + root.data
		if s == sum:
			count[0] += 1
		return s
	subtreecount(root, x)
	return count[0]


count = 0

def funct1(root, x):
	global count
	if root == None:
		return 0
	left = funct1(root.left, x)
	right = funct1(root.right, x)
	if left + right + root.data == x:
		count += 1
	return left + right + root.data

def countSubtreesWithSumX(root, x):
	global count
	count = 0
	funct1(root, x)
	return count


def countSubtreesWithSumX(root, k):

	def helper(root):
		nonlocal ans
		if not root:
			return 0
		lft = helper(root.left)
		rgt = helper(root.right)
		if lft + rgt + root.data == k:
			ans += 1
		return lft + rgt + root.data
	ans = 0
	helper(root)
	return ans


def countSubtreesWithSumXRec(root, x):
	if root == None:
		return (0, 0)
	(ans_l, sum_l) = countSubtreesWithSumXRec(root.left, x)
	(ans_r, sum_r) = countSubtreesWithSumXRec(root.right, x)
	if sum_l + sum_r + root.data == x:
		return (ans_l + ans_r + 1, sum_l + sum_r + root.data)
	else:
		return (ans_l + ans_r, sum_l + sum_r + root.data)

def countSubtreesWithSumX(root, x):
	(ans, sum_t) = countSubtreesWithSumXRec(root, x)
	return ans


def countSubtreesWithSumX(root, x):
	res = [0]

	def dfs(root):
		if not root:
			return 0
		if not root.left and (not root.right):
			if root.data == x:
				res[0] += 1
			return root.data
		l = dfs(root.left)
		r = dfs(root.right)
		if l + r + root.data == x:
			res[0] += 1
		return l + r + root.data
	dfs(root)
	return res[0]


def countSubtreesWithSumX(root, x):
	co = 0

	def solve(root):
		nonlocal co
		if root is None:
			return 0
		l = solve(root.left)
		r = solve(root.right)
		if root.data + l + r == x:
			co += 1
		return root.data + l + r
	solve(root)
	return co


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

def countSubtreesWithSumX(root, x):
	ans = [0]

	def calc(root):
		if root == None:
			return 0
		l = calc(root.left)
		r = calc(root.right)
		if l + r + root.data == x:
			ans[0] += 1
		return l + r + root.data
	calc(root)
	return ans[0]


def countSubtreesWithSumX(root, x):

	def count(root, x, cnt):
		if not root:
			return 0
		lsum = count(root.left, x, cnt)
		rsum = count(root.right, x, cnt)
		local_sum = root.data + lsum + rsum
		if local_sum == x:
			cnt[0] += 1
		return local_sum
	res = [0]
	count(root, x, res)
	return res[0]


def countSubtreesWithSumX(root, x):

	def my(root):
		global c
		if not root:
			return 0
		l = my(root.left)
		r = my(root.right)
		if l + r + root.data == x:
			c += 1
		return l + r + root.data
	global c
	c = 0
	my(root)
	return c


def f(node, x, ans):
	if node is None:
		return 0
	l = f(node.left, x, ans)
	r = f(node.right, x, ans)
	if l + r + node.data == x:
		ans[0] += 1
	return l + r + node.data

def countSubtreesWithSumX(root, x):
	ans = [0]
	f(root, x, ans)
	return ans[0]


def sumi(root, count, x):
	if root is None:
		return 0
	ls = sumi(root.left, count, x)
	rs = sumi(root.right, count, x)
	sumuo = ls + rs + root.data
	if sumuo == x:
		count[0] += 1
	return sumuo

def countSubtreesWithSumX(root, x):
	if root is None:
		return 0
	count = [0]
	ls = sumi(root.left, count, x)
	rs = sumi(root.right, count, x)
	if ls + rs + root.data == x:
		count[0] += 1
	return count[0]


def countSubtreesWithSumX(root, x):

	def traverse(node, k, ans):
		if not node:
			return 0
		sm = traverse(node.left, k, ans) + traverse(node.right, k, ans) + node.data
		if sm == k:
			ans[0] += 1
		return sm
	ans = [0]
	traverse(root, x, ans)
	return ans[0]


from collections import defaultdict

def countSubtreesWithSumX(root, x):

	def idk(root, x):
		if not root:
			return (0, defaultdict(lambda : 0))
		(count, d1) = idk(root.left, x)
		(count2, d2) = idk(root.right, x)
		d = defaultdict(lambda : 0)
		if len(d1) == 0 and len(d2) == 0:
			d[root.data] += 1
			if root.data == x:
				count += 1
		for k1 in d1:
			for k2 in d2:
				if k1 + k2 + root.data == x:
					count += d1[k1] * d2[k2]
				d[k1 + k2 + root.data] += d1[k1] * d2[k2]
		if len(d2) == 0:
			for k1 in d1:
				if k1 + root.data == x:
					count += d1[k1]
				d[k1 + root.data] += d1[k1]
		if len(d1) == 0:
			for k2 in d2:
				if k2 + root.data == x:
					count += d2[k2]
				d[k2 + root.data] += d2[k2]
		return (count + count2, d)
	(ans, _) = idk(root, x)
	return ans


def countSubtreesWithSumX(root, x):
	q = [root]
	d = {}
	while q:
		node = q.pop(0)
		d[node] = -1
		if node.left:
			q.append(node.left)
		if node.right:
			q.append(node.right)

	def sum(root):
		if not root:
			return 0
		if d[root] != -1:
			return d[root]
		d[root] = root.data + sum(root.left) + sum(root.right)
		return d[root]
	count = 0
	sum(root)
	a = list(d.values())
	for i in a:
		if i == x:
			count += 1
	return count


def helper(root, x, val):
	if not root:
		return 0
	s = helper(root.left, x, val) + helper(root.right, x, val) + root.data
	if s == x:
		val[0] += 1
	return s

def countSubtreesWithSumX(root, x):
	val = [0]
	helper(root, x, val)
	return val[0]


def countSubtreesWithSumX(root, x):
	global ptr
	ptr = None

	def solve(root, ans, x):
		global ptr
		if not root:
			return 0
		l = solve(root.left, ans, x)
		r = solve(root.right, ans, x)
		if l + r + root.data == x:
			ans[0] += 1
		if ptr != root:
			return l + root.data + r
	ans = [0]
	solve(root, ans, x)
	return ans[0]


def utility(root, x, res):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		if root.data == x:
			res[0] += 1
		return root.data
	lSum = utility(root.left, x, res)
	rSum = utility(root.right, x, res)
	total = root.data + lSum + rSum
	if total == x:
		res[0] += 1
	return total

def countSubtreesWithSumX(root, x):
	res = [0]
	utility(root, x, res)
	return res[0]


def countSubtreesWithSumX(root, x):
	count = [0]

	def dfs(node, count):
		if not node:
			return 0
		l = dfs(node.left, count)
		r = dfs(node.right, count)
		summ = l + r + node.data
		if summ == x:
			count[0] += 1
		return summ
	dfs(root, count)
	return count[0]