Chhota Bheem wants to eat the maximum number of ladoos in Dholakpur on Independence Day. The houses in Dholakpur are arranged in the form of a binary tree and have ladoos the same as their house number. Chhota Bheem is standing at his home initially. 
Find the maximum ladoos he can eat if he can go to houses within a maximum distance k from his house. The number of ladoos at his home should also be included in the sum.
Note: Every house has distinct ladoos in it. 
Example 1:
Input:
                   1
                 /    \
                2      9
               /      /  \
              4      5     7
            /   \         /  \
           8     19     20    11
          /     /  \
         30   40   50
home = 9, K = 1
Output:
22
Explanation:
Initially Bheem at 9, so sum = 9
In 2nd move he went to 5, sum=9+5=14
In 3rd move he went to 7, sum=14+7=21
In 4th move he went to 1, sum=21+1=22
So within K distance bheem can get 22 ladoos.  
Example 2:
Input:
                   1
                 /    \
                2      9
               /      /  \
              4      5     7
            /   \         /  \
           8     19     20    11
          /     /  \
         30   40   50
home = 40, K = 2
Output:
113
Explanation:
Initially Bheem at 40, so sum = 40
In 2nd move he went to 19, sum=40+19=59
In 3rd move he went to 4, sum=59+4=63
In 4th move he went to 50, sum=63+50=113
So within K distance bheem can get 113 ladoos.
Your Task:
You don't need to read input or print anything. Complete the function ladoos() which takes the root of the tree, home, and K  as input parameters and returns the maximum number of ladoos he can eat.
Expected Time Complexity: O(N), where N is no. of nodes
Expected Space Complexity: O(1)
Constraints:
1 ≤ N, Home ≤ 10^{5}
1 ≤ K ≤ 20

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries
Skill types: Data structures

Range queries
Expected Time Complexity: O(N), where N is no. of nodes
Expected Auxiliary Space: O(1)

Starter code:
'''

# node class:



class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None



'''



class Solution:

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

        # Your code goes here





Solutions:
class Solution:

	def findParent(self, root, mp, vis):
		q = []
		q.append(root)
		while q:
			curr = q.pop(0)
			vis[curr] = 0
			if curr.left:
				mp[curr.left] = curr
				q.append(curr.left)
			if curr.right:
				mp[curr.right] = curr
				q.append(curr.right)

	def ladoos(self, root, home, k):
		mp = {}
		vis = {}
		self.findParent(root, mp, vis)
		q = []
		for (node, parent) in mp.items():
			if node.data == home or parent.data == home:
				if node.data == home:
					q.append([node, 0])
					vis[node] = 1
					break
				if parent.data == home:
					q.append([parent, 0])
					vis[parent] = 1
					break
		sum = q[0][0].data
		while q:
			size = len(q)
			lvl = q[0][1]
			if lvl == k:
				break
			lvl += 1
			for i in range(size):
				(curr, curr_lvl) = q.pop(0)
				if curr.left and vis[curr.left] == 0:
					vis[curr.left] = 1
					sum += curr.left.data
					q.append([curr.left, lvl])
				if curr.right and vis[curr.right] == 0:
					vis[curr.right] = 1
					sum += curr.right.data
					q.append([curr.right, lvl])
				if mp.get(curr) and vis.get(mp[curr]) == 0:
					vis[mp[curr]] = 1
					sum += mp[curr].data
					q.append([mp[curr], lvl])
		return sum


class Solution:

	def ladoos(self, root, home, k):
		graph = {}
		self.preOrder(root, graph, None)
		vis = {}
		for i in graph:
			vis[i] = 0
		temp = graph[home]
		vis[home] = 1
		ans = 0
		while len(temp) > 0 and k > 0:
			k -= 1
			for i in range(len(temp)):
				tempo = temp.pop(0)
				if tempo != None and vis[tempo] == 0:
					vis[tempo] = 1
					ans += tempo
					temp += graph[tempo]
		return ans + home

	def preOrder(self, root, graph, parent):
		if root == None:
			return None
		elif root.data not in graph:
			graph[root.data] = [parent, self.preOrder(root.left, graph, root.data), self.preOrder(root.right, graph, root.data)]
		return root.data


class Solution:

	def ladoos(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]


from collections import deque

class Solution:

	def markParent(self, root, parent, target, tar):
		q = deque()
		q.append(root)
		while q:
			sz = len(q)
			for i in range(sz):
				temp = q.popleft()
				if temp.data == target:
					tar.append(temp)
				if temp.left:
					q.append(temp.left)
					parent[temp.left] = temp
				if temp.right:
					q.append(temp.right)
					parent[temp.right] = temp

	def ladoos(self, root, tar, k):
		target = []
		parent_track = {}
		self.markParent(root, parent_track, tar, target)
		visited = {}
		queue = deque()
		queue.append(target[0])
		visited[target[0]] = True
		curr_level = 0
		ans = 0
		while queue:
			size = len(queue)
			if curr_level > k:
				break
			for i in range(size):
				current = queue.popleft()
				ans += current.data
				if current.left and current.left not in visited:
					queue.append(current.left)
					visited[current.left] = True
				if current.right and current.right not in visited:
					queue.append(current.right)
					visited[current.right] = True
				if parent_track.get(current) and parent_track[current] not in visited:
					queue.append(parent_track[current])
					visited[parent_track[current]] = True
			curr_level += 1
		return ans


class Solution:

	def ladoos(self, root, h, k):
		g = {}
		home = None
		v = set()

		def graph(node):
			nonlocal home
			if not node:
				return
			if node.data == h:
				home = node
			j = node.left
			k = node.right
			if node not in g:
				g[node] = []
			if j:
				if j not in g:
					g[j] = []
				g[j].append(node)
				g[node].append(j)
			if k:
				if k not in g:
					g[k] = []
				g[k].append(node)
				g[node].append(k)
			graph(node.left)
			graph(node.right)
		graph(root)
		q = [(home, 0)]
		i = 0
		res = 0
		while i < len(q):
			(p, r) = q[i]
			if r > k:
				break
			i += 1
			res += p.data
			v.add(p)
			for j in g[p]:
				if j in v:
					continue
				q.append((j, r + 1))
		return res
		return 0


class Solution:

	def helper2(self, root, k):
		if not root or k < 0:
			return 0
		if k == 0:
			return root.data
		l = self.helper2(root.left, k - 1)
		r = self.helper2(root.right, k - 1)
		return l + r + root.data

	def helper(self, root, home, k):
		if not root:
			return (0, -1)
		if root.data == home:
			return (self.helper2(root, k), k - 1)
		(l, kl) = self.helper(root.left, home, k)
		if l:
			if kl >= 0:
				return (self.helper2(root.right, kl - 1) + l + root.data, kl - 1)
			else:
				return (l, -1)
		(r, kr) = self.helper(root.right, home, k)
		if r:
			if kr >= 0:
				return (self.helper2(root.left, kr - 1) + r + root.data, kr - 1)
			else:
				return (r, -1)
		return (0, -1)

	def ladoos(self, root, home, k):
		(res, _) = self.helper(root, home, k)
		return res


class Solution:

	def dfs(self, root, home, k, d, f):
		if d > k:
			return (False, 0)
		FP = False
		if root.data == home:
			f = True
			FP = True
		if f:
			self.ans += root.data
		(lf, rf) = (False, False)
		ld = 0
		rd = 0
		if root.left:
			(lf, ld) = self.dfs(root.left, home, k, d + 1 if f else d, f)
			if lf:
				if ld <= k:
					self.ans += root.data
				if root.right:
					self.dfs(root.right, home, k, ld + 1, lf)
		if not lf and root.right:
			(rf, rd) = self.dfs(root.right, home, k, d + 1 if f else d, f)
			if rf:
				if rd <= k:
					self.ans += root.data
				if root.left:
					self.dfs(root.left, home, k, rd + 1, rf)
		return (lf or rf or FP, ld + 1 if lf else rd + 1 if rf else d + 1 if FP else d)

	def ladoos(self, root, home, k):
		self.ans = 0
		self.dfs(root, home, k, 0, False)
		return self.ans


class Solution:

	def ladoos(self, root, home, k):
		if root is None:
			return 0
		if not root.left and (not root.right):
			if root.data == home:
				return root.data
			return 0
		(temp, q, pos, len1, node) = ({}, deque(), 0, 1, None)
		q.append(root)
		while pos < len1:
			if q[pos].data == home:
				node = q[pos]
				break
			if q[pos].left:
				q.append(q[pos].left)
				(temp[q[pos].left], len1) = (q[pos], len1 + 1)
			if q[pos].right:
				q.append(q[pos].right)
				(temp[q[pos].right], len1) = (q[pos], len1 + 1)
			pos += 1
		(q, sum1, temp1) = (deque(), 0, set())
		q.append([node, 0])
		while q:
			(node, k1) = q.popleft()
			sum1 += node.data
			temp1.add(node)
			if node.left and k1 < k and (node.left not in temp1):
				q.append([node.left, k1 + 1])
			if node.right and k1 < k and (node.right not in temp1):
				q.append([node.right, k1 + 1])
			if node in temp and k1 < k and (temp[node] not in temp1):
				q.append([temp[node], k1 + 1])
		return sum1


class Solution:

	def Show(self, data, type='dict.ad', enabled=False):
		if enabled:
			if type == 'dict.ad':
				for (k, v) in data.items():
					print('Lvl[%d]:' % k, end=' ')
					for e in v:
						print('[data=%r, parent=%r]' % (e[0].data if e[0] else None, e[1].data if e[1] else -1), end=' ')
					print()
			elif type == 'home.data':
				print('home.data: home=%d, level=%d, node=%d' % (data[0], data[1], data[2].data))
			elif type == 'tree.stack':
				for n in data:
					print('[%r]: p=%r, l=%r, r=%r' % (n[0].data if n[0] else None, n[1].data if n[1] else None, n[0].left.data if n[0].left else None, n[0].right.data if n[0].right else None))

	def downq(self, nodes, dis, k, tsum):
		lvl_nodes = []
		if nodes[0]:
			lvl_nodes.append(nodes[0])
		if nodes[1]:
			lvl_nodes.append(nodes[1])
		while dis < k:
			ncnt = len(lvl_nodes)
			for i in range(ncnt):
				n = lvl_nodes.pop(0)
				tsum += n.data
				if n.left:
					lvl_nodes.append(n.left)
				if n.right:
					lvl_nodes.append(n.right)
			dis += 1
		return tsum

	def upq(self, root, stack, dis, k, tsum):
		lvl_nodes = []
		e = stack[root.data]
		prev = e[0]
		parent = e[1]
		usum = 0
		while dis < k and parent:
			usum += parent.data
			lsum = 0
			rsum = 0
			if parent.left and parent.left.data != prev.data:
				lsum = self.downq([parent.left, None], dis + 1, k, 0)
			if parent.right and parent.right.data != prev.data:
				rsum = self.downq([None, parent.right], dis + 1, k, 0)
			usum += lsum + rsum
			prev = parent
			e = stack[parent.data]
			parent = e[1]
			dis += 1
		return usum + tsum

	def buildLevels(self, root, parent, home, level, stack):
		if root is None or home[2]:
			return
		stack[root.data] = [root, parent]
		if root.data == home[0]:
			home[1] = level
			home[2] = root
			return
		self.buildLevels(root.left, root, home, level + 1, stack)
		self.buildLevels(root.right, root, home, level + 1, stack)

	def ladoos(self, root, home, k):
		hdata = [home, 0, None]
		stack = {}
		self.buildLevels(root, None, hdata, 0, stack)
		self.Show(stack, type='tree.stack')
		self.Show(hdata, type='home.data')
		he = stack[home]
		hnode = he[0]
		hpar = he[1]
		dis = 0
		dsum = hnode.data
		next = [hnode.left, hnode.right]
		dsum = self.downq(next, dis, k, dsum)
		usum = self.upq(hnode, stack, dis, k, 0)
		return dsum + usum

	def ladoos_vw(self, root, home, k):
		if root is None:
			return 0
		if not root.left and (not root.right):
			if root.data == home:
				return root.data
			return 0
		(temp, q, pos, len1, node) = ({}, deque(), 0, 1, None)
		q.append(root)
		while pos < len1:
			if q[pos].data == home:
				node = q[pos]
				break
			if q[pos].left:
				q.append(q[pos].left)
				(temp[q[pos].left], len1) = (q[pos], len1 + 1)
			if q[pos].right:
				q.append(q[pos].right)
				(temp[q[pos].right], len1) = (q[pos], len1 + 1)
			pos += 1
		(q, sum1, temp1) = (deque(), 0, set())
		q.append([node, 0])
		while q:
			(node, k1) = q.popleft()
			sum1 += node.data
			temp1.add(node)
			if node.left and k1 < k and (node.left not in temp1):
				q.append([node.left, k1 + 1])
			if node.right and k1 < k and (node.right not in temp1):
				q.append([node.right, k1 + 1])
			if node in temp and k1 < k and (temp[node] not in temp1):
				q.append([temp[node], k1 + 1])
		return sum1

	def ladoos_v1(self, root, home, k):
		hdata = [home, 0, None]
		stack = {}
		self.buildLevels(root, None, hdata, 0, stack)
		self.Show(stack, type='tree.stack')
		self.Show(hdata, type='home.data')
		he = stack[home]
		hnode = he[0]
		hpar = he[1]
		dis = 0
		__sum = hnode.data
		next = [hnode.left, hnode.right]
		__sum = self.down(next, dis, k, __sum)
		dis = 0
		next = [hpar, None]
		parent = hpar.data
		self.Show(stack, type='tree.stack')
		prev = hnode
		while dis < k:
			e = stack[parent]
			parent = e[1].data if e[1] else None
			__sum += e[0].data
			self.Show(stack, type='tree.stack')
			if e[0].left and e[0].left.data != prev.data:
				__sum = self.down([e[0].left, None], dis + 1, k, __sum)
			elif e[0].right and e[0].right.data != prev.data:
				__sum = self.down([e[0].right, None], dis + 1, k, __sum)
			prev = e[0]
			dis += 1
		return __sum


class Solution:

	def findParent(self, root, mp, vis):
		q = []
		q.append(root)
		while q:
			curr = q.pop(0)
			vis[curr] = 0
			if curr.left:
				mp[curr.left] = curr
				q.append(curr.left)
			if curr.right:
				mp[curr.right] = curr


from collections import defaultdict

class Solution:

	def ladoos(self, root, home, k):
		graph = defaultdict(list)

		def dfs(root):
			if root.left:
				graph[root.left.data].append(root.data)
				graph[root.data].append(root.left.data)
				dfs(root.left)
			if root.right:
				graph[root.right.data].append(root.data)
				graph[root.data].append(root.right.data)
				dfs(root.right)
		dfs(root)
		visited = set()
		visited.add(home)
		ans = 0
		queue = deque([home])
		while queue:
			for _ in range(len(queue)):
				q = queue.popleft()
				ans += q
				if k > 0:
					for v in graph[q]:
						if v in visited:
							continue
						visited.add(v)
						queue.append(v)
			if not k:
				break
			k -= 1
		return ans


class Solution:

	def ladoos(self, root, home, k):
		d = {}
		q = deque()
		q.append([root, None])
		house = None
		while len(q) > 0:
			t = q.popleft()
			if t[0].data == home:
				house = t[0]
			if t[0] not in d:
				d[t[0]] = [t[1], t[0].left, t[0].right]
			if t[0].left:
				q.append([t[0].left, t[0]])
			if t[0].right:
				q.append([t[0].right, t[0]])
		s = set()
		q1 = deque()
		q1.append(house)
		k1 = 0
		s1 = 0
		s.add(house)
		while len(q1) > 0:
			k1 = k1 + 1
			if k1 > k + 1:
				return s1
			n = len(q1)
			for i in range(0, n):
				t = q1.popleft()
				s1 = s1 + t.data
				for i1 in d[t]:
					if i1 != None and i1 not in s:
						s.add(i1)
						q1.append(i1)
		return s1


from collections import *

class Solution:

	def f(self, n, k, vis, par):
		if n == None:
			return 0
		vis.add(n)
		if n != -1:
			self.s += n.data
			if k > 0:
				if par[n] not in vis:
					self.f(par[n], k - 1, vis, par)
				if n.left:
					if n.left not in vis:
						self.f(n.left, k - 1, vis, par)
				if n.right:
					if n.right not in vis:
						self.f(n.right, k - 1, vis, par)

	def ladoos(self, root, home, k):
		self.s = 0
		par = defaultdict(int)
		vis = set()
		queue = [[root, -1]]
		var = 0
		while len(queue) != 0:
			(t, p) = queue.pop(0)
			if t.data == home:
				var = t
			par[t] = p
			if t.left:
				queue.append([t.left, t])
			if t.right:
				queue.append([t.right, t])
		self.f(var, k, vis, par)
		return self.s


class Solution:

	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)

	def ladoos(self, root, home, k):
		(Sum, dist) = self.traverse(root, home, k)
		return Sum


from collections import deque

class Solution:

	def ladoos(self, root, home, k):
		target = None

		def pre(root):
			if not root:
				return
			pre(root.left)
			if root.data == home:
				nonlocal target
				target = root
			pre(root.right)

		def sub(root):
			nonlocal mem
			if not root:
				return
			left = sub(root.left)
			right = sub(root.right)
			if left is not None:
				mem[root] = left
			elif right is not None:
				mem[root] = right
			if root in mem:
				return mem[root] + 1
		pre(root)
		mem = {target: 0}
		sub(root)
		trav = deque([(root, mem[root])])
		s = 0
		while trav:
			(cur, h) = trav.popleft()
			if cur not in mem:
				mem[cur] = h
			else:
				h = mem[cur]
			if cur.left:
				trav.append((cur.left, h + 1))
			if cur.right:
				trav.append((cur.right, h + 1))
		for (i, j) in mem.items():
			if j <= k:
				s += i.data
		return s


class Solution:

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

		def fun1(root, k):
			if not root or k < 0:
				return 0
			return root.data + fun1(root.left, k - 1) + fun1(root.right, k - 1)

		def fun(root, home, k):
			if not root:
				return (-1, 0)
			if root.data == home:
				return (k - 1, fun1(root, k))
			else:
				(left, s1) = fun(root.left, home, k)
				(right, s2) = fun(root.right, home, k)
				if left >= 0:
					return (left - 1, fun1(root.right, left - 1) + root.data + s1)
				if right >= 0:
					return (right - 1, fun1(root.left, right - 1) + root.data + s2)
				return (-1, s1 + s2)
		ans = fun(root, home, k)
		return ans[1]


class Solution:

	def ladoos(self, root, home, k):
		start = None

		def par_asgn(node, par):
			nonlocal start
			node.parent = par
			if node.left:
				par_asgn(node.left, node)
			if node.right:
				par_asgn(node.right, node)
			if node.data == home:
				start = node
		par_asgn(root, None)

		def solve(node, dis, prev):
			if dis < 0:
				return 0
			ans = node.data
			for next_node in (node.parent, node.left, node.right):
				if not next_node or next_node == prev:
					continue
				ans += solve(next_node, dis - 1, node)
			return ans
		return solve(start, k, None)


class Solution:

	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)

	def ladoos(self, root, home, k):
		(Sum, dist) = self.traverse(root, home, k)
		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


class Solution:

	def __init__(self):
		self.ans = 0

	def ladoos(self, root, home, k):
		self.ans = 0
		self.solve(root, home, k)
		return self.ans

	def solve(self, root, home, k):
		if root is None:
			return -1
		if root.data == home:
			self.add(root, k)
			return k - 1
		rem = self.solve(root.right, home, k)
		if rem >= 0:
			self.ans += root.data
			self.add(root.left, rem - 1)
			return rem - 1
		rem = self.solve(root.left, home, k)
		if rem >= 0:
			self.ans += root.data
			self.add(root.right, rem - 1)
			return rem - 1
		return -1

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


class Solution:

	def helper(self, node, home, k, reach):
		if not node:
			return 0
		if node.data == home:
			reach = k + 1
		lreach = self.helper(node.left, home, k, reach - 1)
		if lreach > reach and lreach > 1:
			rreach = self.helper(node.right, home, k, lreach - 1)
		else:
			rreach = self.helper(node.right, home, k, reach - 1)
		if rreach > lreach and rreach > 1:
			lreach = self.helper(node.left, home, k, rreach - 1)
		localReach = max(max(lreach, rreach), reach)
		if localReach > 0:
			self.total += node.data
			localReach -= 1
		return localReach

	def ladoos(self, root, home, k):
		self.total = 0
		self.helper(root, home, k, 0)
		return self.total


class Solution:

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

		def _precompute(nd, par):
			nonlocal start
			nd.parent = par
			if nd.left:
				_precompute(nd.left, nd)
			if nd.right:
				_precompute(nd.right, nd)
			if nd.data == home:
				start = nd

		def _solve(nd, dis, prev):
			if dis < 0:
				return 0
			ans = nd.data
			for nex in (nd.parent, nd.left, nd.right):
				if nex is prev or nex is None:
					continue
				ans += _solve(nex, dis - 1, nd)
			return ans
		start = None
		_precompute(root, None)
		ans = _solve(start, k, None)
		return ans


class Solution:

	def ladoos(self, root, home, k):
		dict = {}
		vis = {}

		def rec(root, par):
			if root == None:
				return
			dict[root] = par
			if root.data == home:
				ho[0] = root
			rec(root.left, root)
			rec(root.right, root)
		ho = [root]
		rec(root, None)
		queue = [(ho[0], 0)]
		sum = 0
		while queue:
			curr = queue.pop(0)
			vis[curr[0]] = 1
			sum += curr[0].data
			if curr[1] == k:
				continue
			if curr[0].left and curr[0].left not in vis:
				queue.append((curr[0].left, curr[1] + 1))
			if curr[0].right and curr[0].right not in vis:
				queue.append((curr[0].right, curr[1] + 1))
			if curr[0] in dict and dict[curr[0]] and (dict[curr[0]] not in vis):
				queue.append((dict[curr[0]], curr[1] + 1))
		return sum


class Solution:

	def ladoos(self, root, home, k):
		pMap = {}
		self.fillParentMap(pMap, None, root)
		targetNode = self.searchNode(root, home)
		return self.bfsTraversal(set(), pMap, targetNode, k)

	def fillParentMap(self, pMap, parent, root):
		if root is None:
			return
		pMap[root] = parent
		self.fillParentMap(pMap, root, root.left)
		self.fillParentMap(pMap, root, root.right)

	def searchNode(self, root, target):
		if root is None or root.data == target:
			return root
		left = self.searchNode(root.left, target)
		if left is not None:
			return left
		return self.searchNode(root.right, target)

	def bfsTraversal(self, vis, pMap, root, k):
		sum = 0
		q = []
		q.append(root)
		vis.add(root)
		while len(q) > 0 and k >= 0:
			size = len(q)
			while size > 0:
				curr = q.pop(0)
				par = pMap.get(curr)
				left = curr.left
				right = curr.right
				sum += curr.data
				if par is not None and par not in vis:
					vis.add(par)
					q.append(par)
				if left is not None and left not in vis:
					vis.add(left)
					q.append(left)
				if right is not None and right not in vis:
					vis.add(right)
					q.append(right)
				size -= 1
			k -= 1
		return sum


class Solution:

	def ladoos(self, root, home, k):
		ans = 0

		def sum_node(n, k):
			nonlocal ans
			if not n or k < 0:
				return 0
			ans += n.data
			sum_node(n.left, k - 1)
			sum_node(n.right, k - 1)

		def walk(n):
			nonlocal ans, k
			if not n:
				return (False, 0)
			if n.data == home:
				sum_node(n, k)
				return (True, k - 1)
			(flag, left) = walk(n.left)
			if flag and left >= 0:
				ans += n.data
				sum_node(n.right, left - 1)
				return (flag, left - 1)
			(flag, right) = walk(n.right)
			if flag and right >= 0:
				ans += n.data
				sum_node(n.left, right - 1)
				return (flag, right - 1)
			return (False, 0)
		walk(root)
		return ans


class Solution:

	def ladoos(self, root, home, k):
		ans = 0
		q = []
		q.append(root)
		need = None
		m = {}
		while q:
			s = len(q)
			for i in range(s):
				temp = q.pop(0)
				if temp.data == home:
					need = temp
				if temp.left:
					q.append(temp.left)
					m[temp.left] = temp
				if temp.right:
					q.append(temp.right)
					m[temp.right] = temp
		mm = {}
		q = []
		q.append(need)
		dis = 0
		while q:
			s = len(q)
			for i in range(s):
				temp = q.pop(0)
				mm[temp] = True
				ans += temp.data
				if temp.left and (not mm.get(temp.left)):
					q.append(temp.left)
				if temp.right and (not mm.get(temp.right)):
					q.append(temp.right)
				if m.get(temp) and (not mm.get(m[temp])):
					q.append(m[temp])
			dis += 1
			if dis > k:
				break
		return ans


class Solution:

	def Show(self, data, type='dict.ad', enabled=False):
		if enabled:
			if type == 'dict.ad':
				for (k, v) in data.items():
					print('Lvl[%d]:' % k, end=' ')
					for e in v:
						print('[data=%r, parent=%r]' % (e[0].data if e[0] else None, e[1].data if e[1] else -1), end=' ')
					print()
			elif type == 'home.data':
				print('home.data: home=%d, level=%d, node=%d' % (data[0], data[1], data[2].data))
			elif type == 'tree.stack':
				for n in data:
					print('[%r]: p=%r, l=%r, r=%r' % (n[0].data if n[0] else None, n[1].data if n[1] else None, n[0].left.data if n[0].left else None, n[0].right.data if n[0].right else None))

	def buildLevels(self, root, parent, home, level, stack):
		if root is None or home[2]:
			return
		stack[root.data] = [root, parent]
		if root.data == home[0]:
			home[1] = level
			home[2] = root
			return
		self.buildLevels(root.left, root, home, level + 1, stack)
		self.buildLevels(root.right, root, home, level + 1, stack)

	def down(self, next, dis, k, __sum):
		while dis < k:
			if next[0]:
				__sum += next[0].data
				next[0] = next[0].left
			if next[1]:
				__sum += next[1].data
				next[1] = next[1].right
			dis += 1
		return __sum

	def ladoos(self, root, home, k):
		if root is None:
			return 0
		if not root.left and (not root.right):
			if root.data == home:
				return root.data
			return 0
		(temp, q, pos, len1, node) = ({}, deque(), 0, 1, None)
		q.append(root)
		while pos < len1:
			if q[pos].data == home:
				node = q[pos]
				break
			if q[pos].left:
				q.append(q[pos].left)
				(temp[q[pos].left], len1) = (q[pos], len1 + 1)
			if q[pos].right:
				q.append(q[pos].right)
				(temp[q[pos].right], len1) = (q[pos], len1 + 1)
			pos += 1
		(q, sum1, temp1) = (deque(), 0, set())
		q.append([node, 0])
		while q:
			(node, k1) = q.popleft()
			sum1 += node.data
			temp1.add(node)
			if node.left and k1 < k and (node.left not in temp1):
				q.append([node.left, k1 + 1])
			if node.right and k1 < k and (node.right not in temp1):
				q.append([node.right, k1 + 1])
			if node in temp and k1 < k and (temp[node] not in temp1):
				q.append([temp[node], k1 + 1])
		return sum1

	def ladoos_v1(self, root, home, k):
		hdata = [home, 0, None]
		stack = {}
		self.buildLevels(root, None, hdata, 0, stack)
		self.Show(stack, type='tree.stack')
		self.Show(hdata, type='home.data')
		he = stack[home]
		hnode = he[0]
		hpar = he[1]
		dis = 0
		__sum = hnode.data
		next = [hnode.left, hnode.right]
		__sum = self.down(next, dis, k, __sum)
		dis = 0
		next = [hpar, None]
		parent = hpar.data
		self.Show(stack, type='tree.stack')
		prev = hnode
		while dis < k:
			e = stack[parent]
			parent = e[1].data if e[1] else None
			__sum += e[0].data
			self.Show(stack, type='tree.stack')
			if e[0].left and e[0].left.data != prev.data:
				__sum = self.down([e[0].left, None], dis + 1, k, __sum)
			elif e[0].right and e[0].right.data != prev.data:
				__sum = self.down([e[0].right, None], dis + 1, k, __sum)
			prev = e[0]
			dis += 1
		return __sum


from typing import List, Dict
from collections import deque

class Node:

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

class Solution:

	def __init__(self):
		self.parent = {}

	def get_parent(self, root: Node, home: int, source: List[Node], par: Node) -> None:
		if not root:
			return
		self.parent[root] = par
		if root.data == home:
			source.append(root)
		self.get_parent(root.left, home, source, root)
		self.get_parent(root.right, home, source, root)

	def ladoos(self, root: Node, home: int, k: int) -> int:
		source = []
		self.get_parent(root, home, source, None)
		q = deque()
		q.append(source[0])
		ans = 0
		visited = set()
		visited.add(source[0])
		while q:
			size = len(q)
			for i in range(size):
				cur = q.popleft()
				ans += cur.data
				if cur.left and cur.left not in visited:
					q.append(cur.left)
					visited.add(cur.left)
				if cur.right and cur.right not in visited:
					q.append(cur.right)
					visited.add(cur.right)
				if self.parent[cur] and self.parent[cur] not in visited:
					q.append(self.parent[cur])
					visited.add(self.parent[cur])
			if k == 0:
				break
			k -= 1
		return ans


from typing import List, Tuple, Dict
from collections import deque

class Node:

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

class Solution:

	@staticmethod
	def markParents(r: Node, p: Dict[Node, Node]) -> None:
		q = deque()
		q.append(r)
		q.append(None)
		while q:
			f = q.popleft()
			if f != None:
				if f.left != None:
					q.append(f.left)
					p[f.left] = f
				if f.right != None:
					q.append(f.right)
					p[f.right] = f
			elif q:
				q.append(None)

	@staticmethod
	def searchHome(home: int, r: Node) -> Node:
		if r == None:
			return None
		if r.data == home:
			return r
		left = Solution.searchHome(home, r.left)
		if left != None:
			return left
		return Solution.searchHome(home, r.right)

	@staticmethod
	def ladoos(r: Node, home: int, k: int) -> int:
		p = {}
		Solution.markParents(r, p)
		target = Solution.searchHome(home, r)
		q = deque()
		q.append(target)
		visited = {}
		visited[target] = True
		sum = 0
		sum += home
		currLevel = 0
		while q:
			n = len(q)
			if currLevel == k:
				break
			currLevel += 1
			for i in range(n):
				f = q.popleft()
				if f.left != None and f.left not in visited:
					q.append(f.left)
					sum += f.left.data
					visited[f.left] = True
				if f.right != None and f.right not in visited:
					q.append(f.right)
					sum += f.right.data
					visited[f.right] = True
				if f in p and p[f] not in visited:
					q.append(p[f])
					sum += p[f].data
					visited[p[f]] = True
		return sum


class Solution:

	def ladoos(self, root, home, k):
		parent_child = {}
		ghar = None
		q = deque([root])
		while q:
			node = q.popleft()
			if node.left:
				q.append(node.left)
				parent_child[node.left] = node
			if node.right:
				q.append(node.right)
				parent_child[node.right] = node
			if node.data == home:
				ghar = node
		max_laddu = 0
		q = deque([(ghar, 0)])
		visited = set()
		while q:
			(node, dist) = q.popleft()
			if dist > k:
				break
			if node.left and node.left not in visited:
				q.append((node.left, dist + 1))
			if node.right and node.right not in visited:
				q.append((node.right, dist + 1))
			if node in parent_child and parent_child[node] not in visited:
				q.append((parent_child[node], dist + 1))
			max_laddu += node.data
			visited.add(node)
		return max_laddu


class Solution:

	def ladoos(self, root, home, k):
		pMap = {}
		self.FillParentMap(pMap, None, root)
		targetNode = self.SearchNode(root, home)
		return self.BFSTraversal(set(), pMap, targetNode, k)

	def FillParentMap(self, pMap, parent, root):
		if root is None:
			return
		pMap[root] = parent
		self.FillParentMap(pMap, root, root.left)
		self.FillParentMap(pMap, root, root.right)

	def SearchNode(self, root, target):
		if root is None or root.data == target:
			return root
		left = self.SearchNode(root.left, target)
		if left is not None:
			return left
		return self.SearchNode(root.right, target)

	def BFSTraversal(self, vis, pMap, root, k):
		sm = 0
		q = []
		q.append(root)
		vis.add(root)
		while len(q) > 0 and k >= 0:
			size = len(q)
			while size > 0:
				curr = q.pop(0)
				par = pMap.get(curr)
				left = curr.left
				right = curr.right
				sm += curr.data
				if par is not None and par not in vis:
					vis.add(par)
					q.append(par)
				if left is not None and left not in vis:
					vis.add(left)
					q.append(left)
				if right is not None and right not in vis:
					vis.add(right)
					q.append(right)
				size -= 1
			k -= 1
		return sm


class Solution:

	def findTarget(self, root, home):
		qu = [root]
		while qu:
			curr = qu.pop(0)
			if curr.data == home:
				return curr
			if curr.left != None:
				qu.append(curr.left)
			if curr.right != None:
				qu.append(curr.right)
		return None

	def markParent(self, root, mp):
		qu = [root]
		while qu:
			curr = qu.pop(0)
			if curr.left != None:
				mp[curr.left] = curr
				qu.append(curr.left)
			if curr.right != None:
				mp[curr.right] = curr
				qu.append(curr.right)

	def ladoos(self, root, home, k):
		ans = 0
		parent = {}
		target = self.findTarget(root, home)
		self.markParent(root, parent)
		vis = {target: True}
		qu = [target]
		level = 0
		while len(qu) > 0:
			n = len(qu)
			if level > k:
				break
			else:
				level += 1
			for i in range(n):
				curr = qu.pop(0)
				ans += curr.data
				if curr.left != None and curr.left not in vis:
					qu.append(curr.left)
					vis[curr.left] = True
				if curr.right != None and curr.right not in vis:
					qu.append(curr.right)
					vis[curr.right] = True
				if curr in parent and parent[curr] not in vis:
					qu.append(parent[curr])
					vis[parent[curr]] = True
		return ans