Note: This POTD is a part of Geek Summer Carnival. Solve all POTD consecutively from 5th to 10th April and get a chance to win exclusive discount vouchers on our GfG courses.
Geek is at the geek summer carnival. To unlock discounts on exclusive courses he is given a card with a binary tree, a target node and a positive integer k on it. 
He needs to find the sum of all nodes within a max distance k from target node such that the target node is included in sum.
Example 1:
Input:
target = 9 
k = 1
Binary Tree = 
            1
           /  \
          2    9
        /     /  \
       4     5    7
      /  \       /  \
     8    19    20   11
    /   /   \
  30   40   50
Output: 22
Explanation: 
Nodes within distance 1 from 9 
9 + 5 + 7 + 1 = 22
Example 2:
Input:
target = 40 
k = 2
Binary Tree = 
            1
           /  \
          2    9
        /     /  \
       4     5    7
      /  \       /  \
     8    19    20   11
    /   /   \
  30   40   50
Output: 113
Explanation:
Nodes within distance 2 from 40,
40 + 19 + 50 + 4 = 113
Your Task:
You don't need to read input or print anything. Complete the function sum_at_distK() that takes the root of the given binary tree, target and k as input parameters and return the required sum. 
Expected time complexity: O(n)
Expected space complexity: O(n)
Constraints:
1 <= number of nodes <= 1000
1 <= data in nodes,target <= 10000
1 <= k <= 20

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: '''

# node class:



class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None



'''

class Solution:

    def sum_at_distK(self,root, target, k):

        # code here





Solutions:
class Solution:

	def solve2(self, p, k):
		if not p:
			return
		if k > 0:
			self.ans += p.data
			self.solve2(p.left, k - 1)
			self.solve2(p.right, k - 1)

	def solve(self, p, target, k):
		if not p:
			return (0, -1)
		if p.data == target:
			self.ans += p.data
			self.solve2(p.left, k)
			self.solve2(p.right, k)
			return (1, k)
		left = self.solve(p.left, target, k)
		if left[0] == 1:
			if left[1] > 0:
				self.ans += p.data
				self.solve2(p.right, left[1] - 1)
			return (1, left[1] - 1)
		right = self.solve(p.right, target, k)
		if right[0] == 1:
			if right[1] > 0:
				self.ans += p.data
				self.solve2(p.left, right[1] - 1)
			return (1, right[1] - 1)
		return (0, -1)

	def sum_at_distK(self, root, target, k):
		self.ans = 0
		self.solve(root, target, k)
		return self.ans


class Solution:

	def sum_at_distK(self, root, home, k):

		def findforSubtree(root, dis):
			if root is None or dis < 0:
				return 0
			if dis == 0:
				return root.data
			return root.data + findforSubtree(root.left, dis - 1) + findforSubtree(root.right, dis - 1)

		def solve(root, home, k, ans):
			if root == None:
				return -1
			if root.data == home:
				ans[0] += findforSubtree(root, k)
				return 0
			leftDistance = solve(root.left, home, k, ans)
			rightDistance = solve(root.right, home, k, ans)
			if rightDistance != -1:
				if rightDistance + 1 <= k:
					ans[0] += root.data + findforSubtree(root.left, k - rightDistance - 2)
				return rightDistance + 1
			if leftDistance != -1:
				if leftDistance + 1 <= k:
					ans[0] += root.data + findforSubtree(root.right, k - leftDistance - 2)
				return leftDistance + 1
			return -1
		ans = [0]
		solve(root, home, k, ans)
		return ans[0]


class Solution:

	def makeParentMappings(self, root, mappings):
		if root is None:
			return
		queue = [root]
		while len(queue) != 0:
			node = queue.pop(0)
			if node.left is not None:
				mappings[node.left] = node
				queue.append(node.left)
			if node.right is not None:
				mappings[node.right] = node
				queue.append(node.right)

	def findNode(self, root, target):
		result = None
		if root.data == target:
			result = root
		if not result and root.left is not None:
			result = self.findNode(root.left, target)
		if not result and root.right is not None:
			result = self.findNode(root.right, target)
		return result

	def sum_at_distK(self, root, target, k):
		mappings = {}
		self.makeParentMappings(root, mappings)
		visited = set()
		currLevel = 0
		targetNode = self.findNode(root, target)
		visited.add(targetNode)
		queue = [targetNode]
		while len(queue) != 0:
			if currLevel == k:
				break
			currLevel += 1
			size = len(queue)
			for i in range(size):
				node = queue.pop(0)
				if node.left is not None and node.left not in visited:
					queue.append(node.left)
					visited.add(node.left)
				if node.right is not None and node.right not in visited:
					queue.append(node.right)
					visited.add(node.right)
				if node in mappings and mappings[node] not in visited:
					queue.append(mappings[node])
					visited.add(mappings[node])
		size = len(visited)
		sum_ = 0
		for i in visited:
			sum_ += i.data
		return sum_


from collections import deque

class Solution:

	def makeparent(self, root, target):
		if root.data == target:
			self.node = root
		if root.left:
			self.parent[root.left] = root
			self.makeparent(root.left)
		if root.right:
			self.parent[root.right] = root
			self.makeparent(root.right)

	def makeparent(self, root, target):
		q = deque()
		q.append(root)
		while q:
			top = q.popleft()
			if top.data == target:
				self.node = top
			if top.left:
				self.parent[top.left] = top
				q.append(top.left)
			if top.right:
				self.parent[top.right] = top
				q.append(top.right)

	def sum_at_distK(self, root, target, k):
		self.parent = {root: None}
		self.node = None
		count = 0
		visited = set()
		self.makeparent(root, target)
		q = deque()
		q.append([self.node, 0])
		while q:
			(top, val) = q.popleft()
			visited.add(top)
			if val <= k:
				count += top.data
			if top.left and val < k and (top.left not in visited):
				q.append([top.left, val + 1])
			if top.right and val < k and (top.right not in visited):
				q.append([top.right, val + 1])
			if self.parent[top] and val < k and (self.parent[top] not in visited):
				q.append([self.parent[top], val + 1])
		return count


class Solution:

	def sum_at_distK(self, root, target, k):

		def build_path(node, parent, path):
			if not node:
				return None
			path[node] = parent
			if node.data == target:
				return node
			return build_path(node.left, node, path) or build_path(node.right, node, path)

		def travese(n, k, visited):
			if not n or n in visited or k < 0:
				return
			nonlocal s
			visited.add(n)
			s += n.data
			travese(n.left, k - 1, visited)
			travese(n.right, k - 1, visited)
		path = {}
		start = build_path(root, None, path)
		visited = set()
		s = 0
		while start and k >= 0:
			travese(start, k, visited)
			start = path[start]
			k -= 1
		return s


class Solution:

	def maptoparent(self, root, target):
		q = [root]
		(pos, len1) = (0, 1)
		while pos < len1:
			top = q[pos]
			if top.data == target:
				self.node = top
			if top.left:
				q.append(top.left)
				len1 += 1
				self.parent[top.left] = top
			if top.right:
				q.append(top.right)
				len1 += 1
				self.parent[top.right] = top
			pos += 1

	def computesum(self, k):
		self.sum = self.node.data
		q = [[self.node, k]]
		(pos, len1) = (0, 1)
		visited = {self.node}
		while pos < len1:
			(node, k) = q[pos]
			print('k =', k, node.data)
			if k >= 0:
				if node.left and node.left not in visited:
					self.sum += node.left.data
					q.append([node.left, k - 1])
					len1 += 1
				if node.right and node.right not in visited:
					self.sum += node.right.data
					q.append([node.right, k - 1])
					len1 += 1
				if node in self.parent:
					parent = self.parent[node]
					if parent not in self.visited:
						self.sum += node.parent.data
						q.append([parent, k - 1])
						len1 += 1
			pos += 1
		return self.sum

	def computesum(self, root, k):
		if k < 0 or root is None:
			return
		self.sum += root.data
		self.visited.add(root)
		if root.left not in self.visited:
			self.computesum(root.left, k - 1)
		if root.right not in self.visited:
			self.computesum(root.right, k - 1)
		if root in self.parent:
			parent = self.parent[root]
		else:
			return
		if parent not in self.visited:
			self.computesum(self.parent[root], k - 1)

	def sum_at_distK(self, root, target, k):
		self.parent = {}
		self.sum = 0
		self.node = None
		self.visited = set()
		self.maptoparent(root, target)
		self.computesum(self.node, k)
		return self.sum


class Solution:

	def maptoparent(self, root):
		if root is None:
			return
		if not root.left and (not root.right):
			return
		if root.left:
			self.parent[root.left] = root
			self.maptoparent(root.left)
		if root.right:
			self.parent[root.right] = root
			self.maptoparent(root.right)

	def find(self, root, target):
		if root is None:
			return
		if self.node:
			return
		if root.data == target:
			self.node = root
		self.find(root.left, target)
		self.find(root.right, target)

	def computesum(self, root, k):
		if k < 0 or root is None:
			return
		self.sum += root.data
		self.visited.add(root)
		if root.left not in self.visited:
			self.computesum(root.left, k - 1)
		if root.right not in self.visited:
			self.computesum(root.right, k - 1)
		if root in self.parent:
			parent = self.parent[root]
		else:
			return
		if parent not in self.visited:
			self.computesum(self.parent[root], k - 1)

	def sum_at_distK(self, root, target, k):
		self.parent = {}
		self.sum = 0
		self.node = None
		self.maptoparent(root)
		self.find(root, target)
		self.visited = set()
		self.computesum(self.node, k)
		return self.sum


class Solution:

	def __init__(self):
		self.qe = []
		self.v = []
		self.ans = 0

	def sum_at_distK(self, root, target, k):
		d = {}

		def vo(root):
			q = [root]
			while q:
				n = len(q)
				for i in range(n):
					node = q[0]
					del q[0]
					if node:
						if node.left:
							d[node.left] = node
							q.append(node.left)
						if node.right:
							d[node.right] = node
							q.append(node.right)
		vo(root)

		def f():
			a = 0
			for i in self.qe:
				a += i.data
			return a

		def func(root, k):
			self.qe.append(root)
			self.ans += f()
			while k:
				n = len(self.qe)
				for i in range(n):
					node = self.qe[0]
					del self.qe[0]
					if node:
						if node in d and d[node] not in self.v:
							self.qe.append(d[node])
						if node.left and node.left not in self.v:
							self.qe.append(node.left)
						if node.right and node.right not in self.v:
							self.qe.append(node.right)
						self.v.append(node)
				k6 = f()
				self.ans += k6
				k -= 1

		def io(root, target, k):
			if root is None:
				return
			if root.data == target:
				func(root, k)
				return
			io(root.left, target, k)
			io(root.right, target, k)
		io(root, target, k)
		return self.ans


class Solution:

	def sum_at_distK(self, root, target, k):

		def parent(root):
			nonlocal w, count
			if root == None:
				return None
			if root.left:
				dict1[root.left.data] = root
			if root.right:
				dict1[root.right.data] = root
			if root.data == target:
				w = root
			count += 1
			if root.left:
				parent(root.left)
			if root.right:
				parent(root.right)
		w = None
		count = 0
		dict1 = dict()
		parent(root)
		dict2 = {w.data: 0}
		visited = {}
		list1 = [w]
		i = 0
		total = 0
		while i != count:
			node = list1[i]
			if node.left and node.left not in visited:
				dict2[node.left.data] = dict2[node.data] + 1
				list1.append(node.left)
				if dict2[node.left.data] <= k:
					total += node.left.data
				else:
					break
			if node.right and node.right not in visited:
				dict2[node.right.data] = dict2[node.data] + 1
				list1.append(node.right)
				if dict2[node.right.data] <= k:
					total += node.right.data
				else:
					break
			if node.data in dict1 and dict1[node.data] not in visited:
				dict2[dict1[node.data].data] = dict2[node.data] + 1
				list1.append(dict1[node.data])
				if dict2[dict1[node.data].data] <= k:
					total += dict1[node.data].data
			visited[node] = 1
			i += 1
		return total + target
		total = 0
		for i in dict2:
			if dict2[i] <= k:
				total += i
		return total


class Solution:

	def makeParentMappings(self, root, mappings):
		if root is None:
			return
		queue = [root]
		while len(queue) != 0:
			node = queue.pop(0)
			if node.left is not None:
				mappings[node.left] = node
				queue.append(node.left)
			if node.right is not None:
				mappings[node.right] = node
				queue.append(node.right)

	def findNode(self, root, target):
		result = None
		if root.data == target:
			result = root
		if not result and root.left is not None:
			result = self.findNode(root.left, target)
		if not result and root.right is not None:
			result = self.findNode(root.right, target)
		return result

	def sum_at_distK(self, root, target, k):
		mappings = {}
		self.makeParentMappings(root, mappings)
		visited = set()
		currLevel = 0
		targetNode = self.findNode(root, target)
		visited.add(targetNode)
		queue = [targetNode]
		while len(queue) != 0:
			if currLevel == k:
				break
			currLevel += 1
			size = len(queue)
			for i in range(size):
				node = queue.pop(0)
				if node.left is not None and node.left not in visited:
					queue.append(node.left)
					visited.add(node.left)
				if node.right is not None and node.right not in visited:
					queue.append(node.right)
					visited.add(node.right)
				if node in mappings and mappings[node] not in visited:
					queue.append(mappings[node])
					visited.add(mappings[node])
		size = len(visited)
		sum_ = 0
		for i in visited:
			sum_ += i.data
		return sum_
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input()
		root = buildTree(line)
		line = input().strip().split()
		target = int(line[0])
		k = int(line[1])
		obj = Solution()
		print(obj.sum_at_distK(root, target, k))


class Solution:

	def sum_at_distK(self, root, target, k):
		q = [root]
		hm = {}
		while q:
			t = q.pop(0)
			if t.left:
				q.append(t.left)
				hm[t.left] = t
			if t.right:
				q.append(t.right)
				hm[t.right] = t
			if t.data == target:
				tn = t
		summ = 0
		visited = {tn: 1}
		q = [tn]
		count = 0
		while q and count <= k:
			arr = q[0:]
			for i in range(len(arr)):
				t = q.pop(0)
				summ += t.data
				if t.left and visited.get(t.left) == None:
					q.append(t.left)
					visited[t.left] = 1
				if t.right and visited.get(t.right) == None:
					q.append(t.right)
					visited[t.right] = 1
				if hm.get(t) and visited.get(hm[t]) == None:
					q.append(hm[t])
					visited[hm[t]] = 1
			count += 1
		return summ
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input()
		root = buildTree(line)
		line = input().strip().split()
		target = int(line[0])
		k = int(line[1])
		obj = Solution()
		print(obj.sum_at_distK(root, target, k))


class Solution:

	def sum_at_distK(self, root, target, k):
		parent = dict()
		start = [None]
		self.fillUpParent(root, parent, start, target)
		totalSum = 0
		visited = set()
		queue = [(start[0], 0)]
		while queue:
			(node, currentK) = queue.pop(0)
			if currentK > k:
				continue
			totalSum += node.data
			visited.add(node)
			if node in parent and parent[node] not in visited:
				queue.append((parent[node], currentK + 1))
			if node.left and node.left not in visited:
				queue.append((node.left, currentK + 1))
			if node.right and node.right not in visited:
				queue.append((node.right, currentK + 1))
		return totalSum

	def fillUpParent(self, root, parent, start, target):
		if not root:
			return
		if root.data == target and (not start[0]):
			start[0] = root
		if root.left:
			parent[root.left] = root
		if root.right:
			parent[root.right] = root
		self.fillUpParent(root.left, parent, start, target)
		self.fillUpParent(root.right, parent, start, target)


class Solution:

	def sum_at_distK(self, root, target, k):
		self.targetNode = None
		mp = {}

		def makeparent(root, target):
			if not root:
				return
			if root.data == target:
				self.targetNode = root
			if root.left:
				mp[root.left] = root
			if root.right:
				mp[root.right] = root
			makeparent(root.left, target)
			makeparent(root.right, target)
		makeparent(root, target)
		q = [self.targetNode]
		vis = set()
		res = 0
		while len(q) > 0 and k >= 0:
			n = len(q)
			while n > 0:
				temp = q.pop(0)
				if temp in vis:
					n -= 1
					continue
				vis.add(temp)
				res += temp.data
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				if temp in mp:
					q.append(mp[temp])
				n -= 1
			k -= 1
		return res


class Solution:

	def sum_at_distK(self, root, target, k):
		if root is None:
			return 0

		def findSum(root, k):
			if root is None or k < 0:
				return 0
			return root.data + findSum(root.left, k - 1) + findSum(root.right, k - 1)

		def helper(root, target, k):
			if root is None:
				return (0, -1)
			if root.data == target:
				sm = findSum(root, k)
				return (sm, k - 1)
			(sm, dist) = helper(root.left, target, k)
			if sm > 0:
				if dist == -1:
					return (sm, dist)
				sm = sm + findSum(root.right, dist - 1) + root.data
				return (sm, dist - 1)
			(sm, dist) = helper(root.right, target, k)
			if sm > 0:
				if dist == -1:
					return (sm, dist)
				sm = sm + findSum(root.left, dist - 1) + root.data
				return (sm, dist - 1)
			return (0, -1)
		(sm, dist) = helper(root, target, k)
		return sm


class Solution:

	def findNode_and_fillparent_and_visited(self, root, parent, d, target):
		global node
		if not root:
			return
		d[root] = [parent, False]
		if root.data == target:
			node = root
		self.findNode_and_fillparent_and_visited(root.left, root, d, target)
		self.findNode_and_fillparent_and_visited(root.right, root, d, target)

	def findsum(self, root, k, d):
		if not root:
			return 0
		if d[root][1]:
			return 0
		else:
			d[root][1] = True
		if k == 0:
			return root.data
		return root.data + self.findsum(root.left, k - 1, d) + self.findsum(root.right, k - 1, d) + self.findsum(d[root][0], k - 1, d)

	def sum_at_distK(self, root, target, k):
		global node
		node = None
		d = {}
		self.findNode_and_fillparent_and_visited(root, None, d, target)
		return self.findsum(node, k, d)


from collections import *

class Solution:

	def sum_at_distK(self, root, target, k):
		d = defaultdict(list)
		q = deque([root])
		while q:
			s = q.popleft()
			if s.left:
				d[s.data].append(s.left.data)
				d[s.left.data].append(s.data)
				q.append(s.left)
			if s.right:
				d[s.data].append(s.right.data)
				d[s.right.data].append(s.data)
				q.append(s.right)
		q = deque()
		q.append([target, 0, -1])
		vis = set()
		ans = 0
		vis.add(target)
		while q:
			(s, dist, par) = q.popleft()
			ans += s
			if dist == k:
				continue
			for j in d[s]:
				if j not in vis:
					q.append([j, dist + 1, s])
					vis.add(j)
		return ans


import collections

class Solution:

	def preorder(self, root):
		if not root:
			return
		if root.left:
			self.adj_lst[root.data].append(root.left)
			self.adj_lst[root.left.data].append(root)
			self.preorder(root.left)
		if root.right:
			self.adj_lst[root.data].append(root.right)
			self.adj_lst[root.right.data].append(root)
			self.preorder(root.right)

	def sum_at_distK(self, root, target, k):
		self.adj_lst = collections.defaultdict(list)
		self.preorder(root)
		q = collections.deque()
		q.append([target, k])
		visited = set()
		visited.add(target)
		ans = target
		while q:
			(node, dist) = q.popleft()
			if dist > 0:
				for nodes in self.adj_lst[node]:
					if nodes.data not in visited:
						ans += nodes.data
						visited.add(nodes.data)
						q.append([nodes.data, dist - 1])
		return ans


import collections

class Solution:

	def sum_at_distK(self, root, target, k):

		def dfs(node) -> int:
			if not node:
				return -1
			elif node.data == target:
				inorder(node, 0)
				return 1
			else:
				(L, R) = (dfs(node.left), dfs(node.right))
				if L != -1:
					if L <= k:
						ans.append(node.data)
					inorder(node.right, L + 1)
					return L + 1
				elif R != -1:
					if R <= k:
						ans.append(node.data)
					inorder(node.left, R + 1)
					return R + 1
				else:
					return -1

		def inorder(node, k2):
			if not node:
				return
			if k2 <= k:
				ans.append(node.data)
			if node.left:
				inorder(node.left, k2 + 1)
			if node.right:
				inorder(node.right, k2 + 1)
		ans = []
		dfs(root)
		return sum(ans) if ans else 0


import collections

class Solution:

	def __init__(self):
		self.targets = None

	def sum_at_distK(self, root, target, k):

		def dfs(node, par=None):
			if node:
				node.par = par
				dfs(node.left, node)
				dfs(node.right, node)
		dfs(root)
		self.inorder(root, target)
		queue = collections.deque([(self.targets, 0)])
		seenTarget = {self.targets}
		sums = 0
		while queue:
			if queue[0][1] > k:
				break
			if queue[0][1] <= k:
				sums += queue[0][0].data
			(tops, k2) = queue.popleft()
			for neibors in (tops.left, tops.right, tops.par):
				if neibors and neibors not in seenTarget:
					seenTarget.add(neibors)
					queue.append((neibors, k2 + 1))
		return sums

	def inorder(self, root, target):
		if not root:
			return
		if root.data == target:
			self.targets = root
			return
		if self.targets == None:
			self.inorder(root.left, target)
		if self.targets == None:
			self.inorder(root.right, target)


class Solution:

	def sum_at_distK(self, root, target, k):
		parent = dict()
		target_node = [None]

		def getParent(node, target_node):
			if node is None:
				return
			if node.data == target:
				target_node[0] = node
			parent[node.left] = node
			parent[node.right] = node
			getParent(node.left, target_node)
			getParent(node.right, target_node)
		getParent(root, target_node)

		def solve(node, nodes, k):
			if node is None:
				return
			if k < 0:
				return
			if node in nodes:
				return
			nodes.add(node)
			solve(node.left, nodes, k - 1)
			solve(node.right, nodes, k - 1)
			try:
				solve(parent[node], nodes, k - 1)
			except KeyError:
				pass
		nodes = set()
		solve(target_node[0], nodes, k)
		sum_data = 0
		for node in nodes:
			sum_data += node.data
		return sum_data


class Solution:

	def findparent(self, root, tar, par, parent):
		if not root:
			return None
		par[root] = parent
		if root.data == tar:
			return root
		return self.findparent(root.left, tar, par, root) or self.findparent(root.right, tar, par, root)

	def travel(self, root, k, vis, summ):
		if k >= 0 and root not in vis:
			summ[0] += root.data
			vis.add(root)
		if root.left:
			self.travel(root.left, k - 1, vis, summ)
		if root.right:
			self.travel(root.right, k - 1, vis, summ)

	def sum_at_distK(self, root, tar, k):
		par = {}
		parent = None
		tar = self.findparent(root, tar, par, parent)
		vis = set()
		summ = [0]
		while tar and k >= 0:
			self.travel(tar, k, vis, summ)
			tar = par[tar]
			k -= 1
		return summ[0]


def bfs(root, k):
	if k < 0:
		return 0
	lst = [(root, 0)]
	sum = 0
	while lst != []:
		x = lst.pop(0)
		sum += x[0].data
		if x[0].left != None and x[1] < k:
			lst.append((x[0].left, x[1] + 1))
		if x[0].right != None and x[1] < k:
			lst.append((x[0].right, x[1] + 1))
	return sum

class Solution:

	def sum_at_distK(self, root, target, k):
		parents = {root: None}
		lst = [root]
		result = 0
		x = None
		while lst != []:
			x = lst.pop(0)
			if x.data == target:
				result += bfs(x, k)
				break
			if x.left != None:
				parents[x.left] = x
				lst.append(x.left)
			if x.right != None:
				parents[x.right] = x
				lst.append(x.right)
		temp = x
		depth = k
		for i in range(1, k + 1):
			if parents[temp] != None:
				result += parents[temp].data
				if parents[temp].left != None and parents[temp].left != temp:
					ans = bfs(parents[temp].left, depth - i - 1)
					result += ans
				if parents[temp].right != None and parents[temp].right != temp:
					ans = bfs(parents[temp].right, depth - i - 1)
					result += ans
				temp = parents[temp]
			else:
				break
		return result


class Solution:

	def sum_at_distK(self, root, target, k):

		def findRoute(node, parentNode, routes):
			if not node:
				return
			routes[node] = parentNode
			if node.data == target:
				return node
			return findRoute(node.left, node, routes) or findRoute(node.right, node, routes)

		def travel(n, k, visited):
			if not n or n in visited or k < 0:
				return
			nonlocal s
			visited.add(n)
			s += n.data
			travel(n.left, k - 1, visited)
			travel(n.right, k - 1, visited)
		routes = {}
		initial = findRoute(root, None, routes)
		visited = set()
		s = 0
		while initial and k >= 0:
			travel(initial, k, visited)
			initial = routes[initial]
			k -= 1
		return s


class Solution:

	def sum_at_distK(self, root, target, k):
		ancestor_map = {}
		self.t = None
		self.findTarget(root, target)
		self.get_ancestors(root, ancestor_map, None)
		q = []
		q.append(self.t)
		dist = 0
		visited = set()
		visited.add(self.t)
		ans = target
		if k == 0:
			return [target.val]
		while q:
			if dist == k:
				break
			nextLevel = []
			for node in q:
				if node.left != None and node.left not in visited:
					nextLevel.append(node.left)
					visited.add(node.left)
				if node.right != None and node.right not in visited:
					nextLevel.append(node.right)
					visited.add(node.right)
				if ancestor_map[node] not in visited and ancestor_map[node] != None:
					nextLevel.append(ancestor_map[node])
					visited.add(ancestor_map[node])
			dist += 1
			ans += sum([i.data for i in nextLevel])
			q = nextLevel
		return ans

	def findTarget(self, node, target):
		if node == None:
			return
		if node.data == target:
			self.t = node
			return
		self.findTarget(node.left, target)
		self.findTarget(node.right, target)

	def get_ancestors(self, curr, ancestor_map, ancestor):
		if curr == None:
			return
		ancestor_map[curr] = ancestor
		self.get_ancestors(curr.left, ancestor_map, curr)
		self.get_ancestors(curr.right, ancestor_map, curr)


class Solution:

	def sum_at_distK(self, root, target, k):
		(Sum, dist) = self.traverse(root, target, k)
		return Sum

	def add_subtree(self, n, dist):
		if n is None or dist < 0:
			return 0
		return n.data + self.add_subtree(n.left, dist - 1) + self.add_subtree(n.right, dist - 1)

	def traverse(self, n, target, k):
		if n is None:
			return (0, -1)
		if n.data == target:
			return (self.add_subtree(n, k), k - 1)
		(Sum, dist) = self.traverse(n.left, target, k)
		if Sum > 0:
			if dist == -1:
				return (Sum, dist)
			return (Sum + n.data + self.add_subtree(n.right, dist - 1), dist - 1)
		(Sum, dist) = self.traverse(n.right, target, k)
		if Sum > 0:
			if dist == -1:
				return (Sum, dist)
			return (Sum + n.data + self.add_subtree(n.left, dist - 1), dist - 1)
		return (0, -1)


class Solution:

	def sum_at_distK(self, root, target, k):
		par = {}
		start = None

		def sol(r, prev):
			nonlocal par
			nonlocal start
			if r == None:
				return
			if r.data == target:
				start = r
			if r not in par:
				par[r] = None
			par[r] = prev
			sol(r.left, r)
			sol(r.right, r)
		sol(root, None)
		from collections import deque
		q = deque()
		ans = 0
		q.append((start, 0))
		vis = set()
		while q:
			(cur, dis) = q.popleft()
			if cur not in vis and dis <= k:
				vis.add(cur)
				ans += cur.data
				if par[cur]:
					q.append((par[cur], dis + 1))
				if cur.left:
					q.append((cur.left, dis + 1))
				if cur.right:
					q.append((cur.right, dis + 1))
		return ans


from collections import defaultdict

class Solution:

	def findAndStoreNeighbours(self, root, target, ptr, h, temp):
		if root is None:
			return None
		if root.data == target:
			ptr[0] = root
		left = self.findAndStoreNeighbours(root.left, target, ptr, h, root)
		h[root.data] = [temp.data]
		right = self.findAndStoreNeighbours(root.right, target, ptr, h, root)
		if left:
			h[root.data].append(left.data)
		if right:
			h[root.data].append(right.data)
		return root

	def dfs(self, ptr, h, k, ans, visited):
		if k == 0:
			return 0
		for i in h[ptr]:
			if i not in visited:
				visited.add(i)
				if i != -1:
					ans[0] += i
				self.dfs(i, h, k - 1, ans, visited)
		return ans

	def sum_at_distK(self, root, target, k):
		h = defaultdict(list)
		ptr = [0]
		self.findAndStoreNeighbours(root, target, ptr, h, Node(-1))
		ans = [0]
		visited = set()
		visited.add(target)
		self.dfs(ptr[0].data, h, k, ans, visited)
		return ans[0] + target


class Solution:

	def findTarget(self, root, target, tar, parents):
		if root.data == target:
			tar[0] = root
		if root.left:
			parents[root.left] = root
			self.findTarget(root.left, target, tar, parents)
		if root.right:
			parents[root.right] = root
			self.findTarget(root.right, target, tar, parents)

	def findSum(self, root, k, visited, parents):
		if k == -1 or root is None or root in visited.keys():
			return 0
		visited[root] = True
		return root.data + self.findSum(root.left, k - 1, visited, parents) + self.findSum(root.right, k - 1, visited, parents) + self.findSum(parents[root], k - 1, visited, parents)

	def sum_at_distK(self, root, target, k):
		tar = [None]
		parents = {root: None}
		self.findTarget(root, target, tar, parents)
		visited = {}
		return self.findSum(tar[0], k, visited, parents)


class Solution:

	def inorder(self, root, d, target):
		global pointer
		queue = [root]
		while queue:
			le = len(queue)
			while le > 0:
				current = queue.pop()
				if current.data == target:
					pointer = current
				if current.left:
					d[current.left] = current
					queue.append(current.left)
				if current.right:
					d[current.right] = current
					queue.append(current.right)
				le -= 1

	def sum_at_distK(self, root, target, k):
		global pointer
		pointer = None
		parent_nodes = {}
		self.inorder(root, parent_nodes, target)
		req_sum = 0
		queue = [pointer]
		visited = {}
		visited[pointer] = 1
		curr_level = 0
		while queue:
			le = len(queue)
			if curr_level == k + 1:
				return req_sum
			curr_level += 1
			while le > 0:
				p = queue.pop(0)
				req_sum += p.data
				if p in parent_nodes and parent_nodes[p] not in visited:
					queue.append(parent_nodes[p])
					visited[parent_nodes[p]] = 1
				if p.left and p.left not in visited:
					queue.append(p.left)
					visited[p.left] = 1
				if p.right and p.right not in visited:
					queue.append(p.right)
					visited[p.right] = 1
				le -= 1
		return req_sum