Given a Binary Tree of size N, find the sum of all the leaf nodes that are at minimum level of the given binary tree.
Example 1:
Input: 
         1
        /  \
       2    3
     /  \     \
    4    5     8 
  /  \ 
 7    2      
Output:
sum = 5 + 8 = 13
Example 2:
Input: 
            1
      /    \
     2      3
    / \    / \
   4   5  6   7
Output: 22
Your Task:
You don't need to read input or print anything. Your task is to complete the function minLeafSum() which takes root node of the tree as input parameter and returns an integer denoting the sum of all the leaf nodes that are at minimum level of the given binary tree. If the tree is empty, return 0. 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=N<=10^{3}
1<=data on node<=10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self,val):
        self.data=val
        self.left=None
        self.right=None
'''
class Solution:
    def minLeafSum(self,root):
        #code here

Solutions:
class Solution:

	def minLeafSum(self, root):

		def t(rt, lev):
			nonlocal sum1, mini
			if rt is None:
				return None
			if rt.left is None and rt.right is None:
				if lev < mini:
					sum1 = rt.data
					mini = lev
				elif lev == mini:
					sum1 += rt.data
			t(rt.left, lev + 1)
			t(rt.right, lev + 1)
		(sum1, mini) = (0, 9999)
		t(root, 0)
		return sum1


from collections import deque

class Solution:

	def minLeafSum(self, root):
		queue = deque()
		queue.append(root)
		level = 0
		leaf_sum = 0
		flag = False
		while queue:
			size = len(queue)
			for _ in range(size):
				curr = queue.popleft()
				if not curr.left and (not curr.right):
					leaf_sum += curr.data
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			if leaf_sum > 0:
				return leaf_sum
		return -1


class Solution:

	def minLeafSum(self, root):
		l = [root, 'a']
		p = 0
		res = 0
		while True:
			w = l.pop(0)
			while w != 'a':
				if w.left == None and w.right == None:
					p = 1
					res += w.data
				if w.left:
					l.append(w.left)
				if w.right:
					l.append(w.right)
				w = l.pop(0)
			if p == 1:
				return res
			l.append('a')


class Solution:

	def fun(self, root, level, l):
		if root == None:
			return
		if level >= len(l):
			l.append([])
		if root.left == None and root.right == None:
			l[level].append('R')
			l[level].append(root.data)
		else:
			l[level].append(root.data)
		self.fun(root.left, level + 1, l)
		self.fun(root.right, level + 1, l)

	def minLeafSum(self, root):
		l = []
		self.fun(root, 0, l)
		(s, t) = (0, 0)
		for i in l:
			if 'R' in i:
				t = i
				break
		for i in range(len(t)):
			if t[i] == 'R':
				s += t[i + 1]
		return s


class Solution:

	def solve(self, root, dic, l):
		if root == None:
			return
		if root.left == None and root.right == None:
			if l not in dic:
				dic[l] = root.data
			else:
				dic[l] += root.data
		l += 1
		self.solve(root.left, dic, l)
		self.solve(root.right, dic, l)
		l -= 1

	def minLeafSum(self, root):
		dic = {}
		self.solve(root, dic, 0)
		k = dic.keys()
		k = list(k)
		k.sort()
		return dic[k[0]]


class Solution:

	def printlevel(self, root, level, dict1):
		if root is None:
			return
		if root.left is None and root.right is None:
			if level not in dict1:
				dict1[level] = root.data
			else:
				dict1[level] += root.data
		self.printlevel(root.left, level + 1, dict1)
		self.printlevel(root.right, level + 1, dict1)

	def minLeafSum(self, root):
		dict1 = {}
		level = 0
		self.printlevel(root, level, dict1)
		mylist1 = list(dict1.keys())
		mylist1.sort()
		return dict1[mylist1[0]]


class Solution:

	def minLeafSum(self, root):

		def traversal(root, level):
			nonlocal sum1, minimum
			if root == None:
				return None
			if root.left == None and root.right == None:
				if level < minimum:
					sum1 = root.data
					minimum = level
				elif level == minimum:
					sum1 += root.data
			if root.left:
				traversal(root.left, level + 1)
			if root.right:
				traversal(root.right, level + 1)
		(sum1, minimum) = (0, 999)
		traversal(root, 0)
		return sum1


class Solution:

	def minLeafSum(self, root):
		st = []
		ans = 0
		if root is None:
			return node.data
		st.append(root)
		while len(st) > 0:
			t = []
			while len(st) != 0:
				x = st.pop()
				if x.left is None and x.right is None:
					ans += x.data
				if x.left is not None:
					t.append(x.left)
				if x.right is not None:
					t.append(x.right)
			if ans > 0:
				return ans
			st = t
		return ans


class Solution:

	def trav(self, root, dp, l):
		if root == None:
			return
		if root.left == root.right == None:
			if dp.get(l) == None:
				dp[l] = 0
			dp[l] += root.data
		self.trav(root.left, dp, l + 1)
		self.trav(root.right, dp, l + 1)

	def minLeafSum(self, root):
		dp = dict()
		self.trav(root, dp, 0)
		return dp[min(dp.keys())]


class Solution:

	def minLeafSum(self, root):
		lis = []
		q = []
		q.append(root)
		while q:
			l = len(q)
			for i in range(l):
				temp = q.pop(0)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				if temp.left == None and temp.right == None:
					lis.append(temp.data)
			if len(lis):
				break
		if len(lis):
			return sum(lis)
		else:
			return 0


class Solution:

	def minLeafSum(self, root):
		q = deque()
		q.append(root)
		while len(q) > 0:
			count = len(q)
			total = 0
			flag = False
			while count > 0:
				num = q.popleft()
				if num.left is None and num.right is None:
					flag = True
					total += num.data
				if num.left != None:
					q.append(num.left)
				if num.right != None:
					q.append(num.right)
				count -= 1
			if flag:
				break
		return total


class Solution:

	def minLeafSum(self, root):
		sum_var = 0
		level = 1
		q = []
		q.append(root)
		while len(q) != 0:
			for i in range(len(q)):
				node = q.pop(0)
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
				if node.left == None and node.right == None:
					sum_var += node.data
			level += 1
			if sum_var > 0:
				break
		return sum_var


import collections

class Solution:

	def minLeafSum(self, root):
		s = 0
		q = collections.deque([root])
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if node.left == None and node.right == None:
					s += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if s != 0:
				break
		return s


class Solution:

	def minLeafSum(self, root):
		q = []
		level = 0
		sum = 0
		min_level = 1000
		q.append(root)
		q.append('$')
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					q.append('$')
					level += 1
			else:
				if t.left is None and t.right is None:
					if min_level >= level:
						min_level = level
						sum += t.data
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return sum


from collections import Counter

class Solution:

	def minLeafSum(self, root):
		c = Counter()
		self.myFunc(root, c, 0)
		return c[min(c.keys())]

	def myFunc(self, root, c, level):
		if not root:
			return
		level += 1
		if not root.left and (not root.right):
			c[level] += root.data
		self.myFunc(root.left, c, level)
		self.myFunc(root.right, c, level)
		return


class Solution:

	def minLeafSum(self, root):
		global k
		global l
		l = 1000
		k = root

		def sol(root, level):
			global l
			if not root:
				return 0
			if l > level and (root.left == None and root.right == None):
				l = level
			sol(root.left, level + 1)
			sol(root.right, level + 1)
			return l
		p = sol(root, 0)
		global s
		s = 0
		root = k

		def s1(root, level):
			global s
			if not root:
				return 0
			if level == p and (root.left == None and root.right == None):
				s = s + root.data
			s1(root.left, level + 1)
			s1(root.right, level + 1)
		s1(root, 0)
		return s


class Solution:

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

	def trav(self, root, l):
		if root != None and root.left == None and (root.right == None):
			if l in self.level:
				self.level[l].append(root.data)
			else:
				self.level[l] = [root.data]
		if root.left != None:
			self.trav(root.left, l + 1)
		if root.right != None:
			self.trav(root.right, l + 1)

	def minLeafSum(self, root):
		self.trav(root, 0)
		for l in sorted(self.level.keys()):
			return sum(self.level[l])


class Solution:

	def minLeafSum(self, root):
		if not root:
			return 0
		curr = [root]
		has_leaf = False
		ans = 0
		while curr:
			next_level = []
			while curr:
				v = curr.pop(0)
				if not v.left and (not v.right):
					has_leaf = True
					ans += v.data
				if v.left:
					next_level.append(v.left)
				if v.right:
					next_level.append(v.right)
			if has_leaf:
				return ans
			curr = next_level
		return 0


class Solution:

	def minLeafSum(self, root):
		d = {}
		level = 0
		self.helper(root, level, d)
		d1 = sorted(d.keys())
		return sum(d[d1[0]])

	def helper(self, root, level, d):
		if not root:
			return
		if not root.left and (not root.right):
			if level not in d:
				d[level] = [root.data]
			else:
				d[level].append(root.data)
		self.helper(root.left, level + 1, d)
		self.helper(root.right, level + 1, d)


class queue:

	def __init__(self):
		self.lists = deque()
		self.size = 0

	def enqueue(self, data):
		self.lists.append(data)
		self.size += 1

	def dequeue(self):
		if self.size == 0:
			return -1
		else:
			temp = self.lists.popleft()
			self.size -= 1
			return temp

	def isempty(self):
		return self.size == 0

class Solution:

	def getLeafNodes(self, root):
		q = queue()
		q.enqueue(root)
		result = []
		while q.isempty() != True:
			count = q.size
			while count != 0:
				temp = q.dequeue()
				if temp.left:
					q.enqueue(temp.left)
				if temp.right:
					q.enqueue(temp.right)
				if temp.left == None and temp.right == None:
					result.append(temp.data)
				count -= 1
			if len(result):
				break
		return sum(result)

	def minLeafSum(self, root):
		return self.getLeafNodes(root)


from collections import deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from operator import itemgetter

class Solution:

	def minLeafSum(self, root):
		h = []

		def mls(level, root):
			nonlocal h
			if root is None:
				return None
			if root.right is None and root.left is None:
				h.append((level, root.data))
				return
			return (mls(level + 1, root.right), mls(level + 1, root.left))
		mls(0, root)
		h = sorted(h, key=itemgetter(0))
		x = h[0]
		h = h[1:]
		su = x[1]
		while len(h) > 0:
			y = h[0]
			if y[0] == x[0]:
				su = su + y[1]
				h = h[1:]
			else:
				break
		return su


class Solution:

	def minLeafSum(self, root):

		def helper(x):
			ans = 0
			c = True
			q = []
			if not x:
				return ans
			q.append(x)
			while c and q:
				for i in range(len(q)):
					a = q.pop(0)
					if not a.left and (not a.right):
						ans += a.data
						c = False
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
			return ans
		a = helper(root)
		return a


from math import inf
INF = inf

class Solution:

	def minLeafSum(self, root):

		def dfs_level(node, level):
			if not node:
				return INF
			if not (node.left or node.right):
				return level
			return min(dfs_level(node.left, level + 1), dfs_level(node.right, level + 1))

		def dfs_sum(node, level, min_level):
			if not node or level > min_level:
				return 0
			if not (node.left or node.right):
				return node.data
			return dfs_sum(node.left, level + 1, min_level) + dfs_sum(node.right, level + 1, min_level)
		min_level = dfs_level(root, 0)
		return dfs_sum(root, 0, min_level)


class Solution:

	def minLeafSum(self, root):
		list1 = []

		def height(root):
			if root == None:
				return 0
			return max(height(root.left), height(root.right)) + 1
		height_tree = height(root)

		def print_current_level(root, level):
			nonlocal list1
			if root == None:
				return 0
			elif level == 1 and root.left == None and (root.right == None):
				list1.append(root.data)
				return list1
			elif level > 1:
				print_current_level(root.left, level - 1)
				print_current_level(root.right, level - 1)
		for i in range(1, height_tree + 1):
			print_current_level(root, i)
			if list1:
				break
		sum = 0
		for i in list1:
			sum += i
		return sum


from collections import deque

class Solution:

	def minLeafSum(self, root):
		if root is None:
			return 0
		q = deque()
		q.append(root)
		ans = 0
		Sum = 0
		while q:
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if node.left is None and node.right is None:
					Sum = Sum + node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if Sum > 0:
				return Sum
		return 0


class Solution:

	def minLeafSum(self, root):
		q = []
		s = 0
		q.append(root)
		while q != []:
			n = len(q)
			for i in range(n):
				temp = q.pop(0)
				if temp.left == None and temp.right == None:
					s += temp.data
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			if s != 0:
				return s
		return -1


class Solution:

	def minLeafSum(self, root):
		s1 = 0
		i = 0
		queue = [root]
		level = []
		while queue != [] and root is not None:
			l = []
			for node in queue:
				if node.left is None and node.right is None:
					i = 1
					s1 += node.data
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			if i == 1:
				break
			queue = level
			level = []
		return s1


class Node:

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

class Solution:

	def minLeafSum(self, root):
		count = 0
		d = {}
		if root is None:
			return 0
		else:
			sumi = 0
			import collections
			q = collections.deque()
			q.append(root)
			while q:
				for i in range(len(q)):
					node = q.popleft()
					if node.left == None and node.right == None:
						if count in d:
							d[count].append(node.data)
						else:
							d[count] = [node.data]
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				count += 1
			minimum_level = min(list(d.keys()))
			for key in list(d.keys()):
				if key == minimum_level:
					for x in d[key]:
						sumi += x
			return sumi


class Solution:

	def minLeafSum(self, root):
		if root == None:
			return None
		q = [root]
		sum = 0
		while len(q) > 0:
			count = len(q)
			for i in range(count):
				temp = q.pop(0)
				if temp.left == None and temp.right == None:
					sum += temp.data
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			if sum != 0:
				return sum


class Solution:

	def minLeafSum(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return root.data
		Queue = deque()
		sum = f = 0
		Queue.append(root)
		while not f:
			nc = len(Queue)
			while nc:
				top = Queue.popleft()
				if not top.left and (not top.right):
					sum += top.data
					f = 1
				else:
					if top.left:
						Queue.append(top.left)
					if top.right:
						Queue.append(top.right)
				nc -= 1
		return sum


class Solution:

	def minLeafSum(self, root):
		q = [[root, 0]]
		c = 0
		s = {}
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			f = 0
			if t.left:
				f = 1
				q.append([t.left, g + 1])
			if t.right:
				f = 1
				q.append([t.right, g + 1])
			if f == 0:
				if g in s:
					s[g] += t.data
				else:
					s[g] = t.data
			c += 1
		g = min(s)
		return s[g]


from collections import deque

class Solution:

	def minLeafSum(self, root):
		q = deque([root])
		while q:
			n = len(q)
			suma = 0
			for i in range(n):
				curr = q.popleft()
				if curr.left == None and curr.right == None:
					suma += curr.data
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
			if suma != 0:
				return suma


from collections import deque

class Solution:

	def minLeafSum(self, root):
		queue = deque()
		queue.append(root)
		while len(queue):
			k = len(queue)
			sum = 0
			while k != 0:
				temp = queue.popleft()
				if temp.left == None and temp.right == None:
					sum += temp.data
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
				k -= 1
			if sum != 0:
				return sum
		return -1


class Solution:
	from collections import deque

	def minLeafSum(self, root):
		q = deque()
		ans = 0
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return root.data
		q.append(root)
		while len(q) != 0:
			count = len(q)
			while count != 0:
				count -= 1
				r = q.popleft()
				if r.left is None and r.right is None:
					ans += r.data
				if r.left is not None:
					q.append(r.left)
				if r.right is not None:
					q.append(r.right)
			if ans > 0:
				return ans
		return ans


class Solution:

	def minLeafSum(self, root):
		res = 0
		q = []
		q.append(root)
		while len(q):
			count = len(q)
			ans = []
			while count:
				temp = q.pop(0)
				if temp.left is None and temp.right is None:
					res += temp.data
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				count -= 1
			if res != 0:
				return res
		return 0


class Solution:

	def minLeafSum(self, root):
		arr = [root]
		while len(arr):
			size = len(arr)
			sum1 = 0
			for i in range(size):
				node = arr.pop(0)
				if node.left == None and node.right == None:
					sum1 += node.data
				if node.left:
					arr.append(node.left)
				if node.right:
					arr.append(node.right)
			if sum1 != 0:
				return sum1
		return -1


class Solution:

	def minLeafSum(self, root):
		arr = []
		arr.append(root)
		while len(arr) != 0:
			size = len(arr)
			sum1 = 0
			for i in range(size):
				temp = arr.pop(0)
				if temp.left == None and temp.right == None:
					sum1 += temp.data
				if temp.left:
					arr.append(temp.left)
				if temp.right:
					arr.append(temp.right)
			if sum1 != 0:
				return sum1
		return -1
from collections import deque

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = 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__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.minLeafSum(root)
		print(res)


class Solution:

	def minLeafSum(self, root):
		from collections import deque
		l = deque()
		l.append([root, 0])
		ans = 0
		last_height = -1
		while len(l):
			(curr, level) = l.popleft()
			if last_height == -1 or last_height == level:
				if curr.left == None and curr.right == None:
					last_height = level
					ans += curr.data
				else:
					if curr.left:
						l.append([curr.left, level + 1])
					if curr.right:
						l.append([curr.right, level + 1])
			else:
				break
		return ans
from collections import deque

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = 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__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.minLeafSum(root)
		print(res)


class Solution:

	def solve(self, root, d, level):
		if not root:
			return
		self.solve(root.left, d, level + 1)
		self.solve(root.right, d, level + 1)
		if not root.left and (not root.right):
			if level not in d:
				d.update({level: root.data})
			else:
				d[level] += root.data

	def minLeafSum(self, root):
		d = {}
		level = 0
		self.solve(root, d, level)
		return d[min(d.keys())]
from collections import deque

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = 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__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.minLeafSum(root)
		print(res)


class Solution:

	def minLeafSum(self, root):
		(min_level, leaf_sum) = (float('inf'), 0)
		(que, level) = (deque([root]), 0)
		while que:
			n = len(que)
			for _ in range(n):
				curr = que.popleft()
				if not curr.left and (not curr.right):
					if level <= min_level:
						min_level = level
						leaf_sum += curr.data
				if curr.left:
					que.append(curr.left)
				if curr.right:
					que.append(curr.right)
			level += 1
		return leaf_sum
from collections import deque

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = 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__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.minLeafSum(root)
		print(res)


class Solution:

	def minLeafSum(self, root):

		def fun(r, d, y):
			if r is None:
				return d
			if r.left is None and r.right is None:
				if d.get(y) is None:
					d[y] = r.data
				else:
					d[y] = r.data + d[y]
				return d
			else:
				d = fun(r.left, d, y + 1)
				d = fun(r.right, d, y + 1)
				return d
		res = fun(root, {}, 0)
		return res[min(res.keys())]


class Solution:

	def minLeafSum(self, root):
		q = []
		d = {}
		q.append(root)
		level = 1
		while len(q):
			count = len(q)
			while count > 0:
				p = q.pop(0)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				if p.right == None and p.left == None:
					if level not in list(d.keys()):
						d[level] = [p.data]
					else:
						d[level].append(p.data)
				count -= 1
			level += 1
		m = min(list(d.keys()))
		return sum(d[m])


from queue import Queue

class Solution:

	def minlevel(self, root, level):
		if not root:
			return float('inf')
		if root and (not root.left) and (not root.right):
			return level
		levelr = level
		lefty = self.minlevel(root.left, level + 1)
		righty = self.minlevel(root.right, levelr + 1)
		return min(lefty, righty)

	def minLeafSum(self, root):
		level = 1
		level = self.minlevel(root, level)
		q = Queue()
		q.put(root)
		while level:
			n = q.qsize()
			res = []
			for i in range(n):
				temp = q.get()
				if not temp.left and (not temp.right):
					res.append(temp.data)
				if temp.left:
					q.put(temp.left)
				if temp.right:
					q.put(temp.right)
			level -= 1
		return sum(res)


from collections import deque

class Solution:

	def minLeafSum(self, root):
		queue = deque()
		sum = 0
		queue.append(root)
		is_flag = False
		while not is_flag:
			level_size = len(queue)
			for i in range(level_size):
				node = queue.popleft()
				if not node.left and (not node.right):
					sum = sum + node.data
					is_flag = True
				else:
					if node.left:
						queue.append(node.left)
					if node.right:
						queue.append(node.right)
		return sum


from collections import deque

class Solution:

	def minLeafSum(self, root):
		if not root:
			return
		q = deque()
		level = []
		q.append(root)
		sum = 0
		i = 0
		while q and root is not None:
			for node in q:
				if node.left is None and node.right is None:
					i = 1
					sum += node.data
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			if i == 1:
				break
			q = level
			level = []
		return sum


class Solution:

	def fun(self, root, level, d):
		if root == None:
			return
		if root.left == None and root.right == None:
			if level not in d.keys():
				d[level] = root.data
			else:
				d[level] += root.data
		self.fun(root.left, level + 1, d)
		self.fun(root.right, level + 1, d)

	def minLeafSum(self, root):
		level = 0
		d = {}
		if root == None:
			return 0
		self.fun(root, level, d)
		first_index = min(d.keys())
		return d[first_index]


class Solution:

	def minLeafSum(self, root):
		q = []
		q.append([root, 0])
		if root is None:
			return 0
		Dict = {}
		while q:
			(node, lvl) = q.pop(0)
			if node is not None:
				if node.left is not None:
					if node.left.left is None and node.left.right is None:
						if lvl not in Dict:
							Dict[lvl] = node.left.data
						else:
							Dict[lvl] += node.left.data
				if node.right is not None:
					if node.right.left is None and node.right.right is None:
						if lvl not in Dict:
							Dict[lvl] = node.right.data
						else:
							Dict[lvl] += node.right.data
			if node.left is not None:
				q.append([node.left, lvl + 1])
			if node.right is not None:
				q.append([node.right, lvl + 1])
		if len(Dict) > 0:
			sortedDict = sorted(Dict.items(), key=lambda x: x[0])
			return sortedDict[0][1]
		else:
			return root.data


class Solution:

	def minLeafSum(self, root):
		min_t = [-1, 0]
		self.helper(root, 0, min_t)
		return min_t[1]

	def helper(self, root, level, min_t):
		if root is None:
			return
		if root.left is None and root.right is None:
			if min_t[0] == -1 or level == min_t[0]:
				min_t[0] = level
				min_t[1] += root.data
			elif level < min_t[0]:
				min_t[0] = level
				min_t[1] = root.data
			return
		self.helper(root.left, level + 1, min_t)
		self.helper(root.right, level + 1, min_t)


class Solution:

	def helper(self, q, d):
		while len(q) != 0:
			(p, l) = q.pop(0)
			if not p.left and (not p.right):
				if l not in d:
					d[l] = []
				d[l].append(p.data)
			if p.left:
				q.append((p.left, l + 1))
			if p.right:
				q.append((p.right, l + 1))

	def minLeafSum(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return root.data
		d = {}
		self.helper([(root, 0)], d)
		return sum(d.get(sorted(d.keys())[0]))


class Solution:

	def minLeafSum(self, root):
		if root is None:
			return 0
		res = 0
		curr_leaves = []
		q = [root, None]
		while q:
			t = q.pop(0)
			if t is None:
				if curr_leaves:
					res = sum(curr_leaves)
					break
				curr_leaves = []
				if not q:
					break
				q.append(None)
			else:
				if t.left is None and t.right is None:
					curr_leaves.append(t.data)
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return res


class Solution:

	def minLeafSum(self, root):
		if root is None:
			return 0
		q = []
		q.append(root)
		total = 0
		while len(q):
			s = len(q)
			for i in range(s):
				t = q.pop(0)
				if t.left is None and t.right is None:
					total += t.data
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			if total > 0:
				break
		return total


class Solution:

	def minLeafSum(self, root):
		sum = 0
		q = []
		level = 0
		f = 0
		q.append(root)
		while f == 0:
			nc = len(q)
			while nc:
				node = q.pop(0)
				if not node.left and (not node.right):
					sum += node.data
					f = 1
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				nc -= 1
		return sum


from collections import defaultdict

class Solution:

	def minLeafSum(self, root):
		if root is None:
			return []
		d = defaultdict(list)

		def bfs(node, level):
			if not node:
				return
			if node.left is None and node.right is None:
				d[level].append(node.data)
			bfs(node.left, level + 1)
			bfs(node.right, level + 1)
		bfs(root, 0)
		min_key = min(list(d.keys()))
		return sum(list(d.get(min_key)))


import collections

class Solution:

	def minLeafSum(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		q = collections.deque()
		q.append(root)
		summ = 0
		flag = 0
		while flag == 0:
			for i in range(len(q)):
				node = q.popleft()
				if node:
					if node.left == None and node.right == None:
						summ += node.data
						flag = 1
					else:
						if node.left:
							q.append(node.left)
						if node.right:
							q.append(node.right)
			if flag == 1:
				break
		return summ


class Solution:

	def __init__(self):
		self.minlevel = 10 ** 9 + 7
		self.res = 0

	def minLeafSum(self, root):
		self.leaflevel(root, 1)
		self.helper(root, 1)
		return self.res

	def helper(self, root, level):
		if root == None:
			return
		if root.left == None and root.right == None:
			if level == self.minlevel:
				self.res += root.data
		self.helper(root.left, level + 1)
		self.helper(root.right, level + 1)
		return

	def leaflevel(self, root, level):
		if root == None:
			return
		if root.left == None and root.right == None:
			if level < self.minlevel:
				self.minlevel = level
		self.leaflevel(root.left, level + 1)
		self.leaflevel(root.right, level + 1)


class Solution:

	def minLeafSum(self, root):
		if root is None:
			return 0
		q = []
		q.append(root)
		ans = []
		anspro = []
		while len(q) > 0:
			n = len(q)
			level = []
			for i in range(n):
				node = q.pop(0)
				if node.left == None and node.right == None:
					level.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			ans.append(level)
		for i in ans:
			if i != []:
				anspro.append(i)
		return sum(anspro[0])


class Solution:

	def minLeafSum(self, root):
		sum = 0
		q = [root]
		while q:
			count = len(q)
			while count > 0:
				temp = q.pop(0)
				if temp.left == None and temp.right == None:
					sum += temp.data
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				count -= 1
				if count == 0 and sum > 0:
					break
			if sum > 0:
				break
		return sum


class Solution:

	def minLeafSum(self, root):

		def height(root):
			if root == None:
				return 0
			left = height(root.left)
			right = height(root.right)
			return max(left, right) + 1

		def traversal(root, level):
			nonlocal total
			if root == None:
				return None
			if level == 0:
				if root.left == None and root.right == None:
					total += root.data
			else:
				traversal(root.left, level - 1)
				traversal(root.right, level - 1)
		tall = height(root)
		total = 0
		for i in range(tall):
			traversal(root, i)
			if total != 0:
				return total


class Solution:

	def __init__(self):
		self.d = {}
		self.level_min = None

	def _min_leaf_sum(self, root, h):
		if not root:
			return None
		if self.level_min and h > self.level_min:
			return None
		if not root.left and (not root.right):
			self.level_min = h
			self.d[h] = self.d.get(h, 0) + root.data
		self._min_leaf_sum(root.left, h + 1)
		self._min_leaf_sum(root.right, h + 1)

	def minLeafSum(self, root):
		self._min_leaf_sum(root, 1)
		return self.d[self.level_min]


from collections import deque

class Solution:

	def minLeafSum(self, root):
		isleaf = 0
		if not root:
			return 0
		if not root.left and (not root.right):
			return root.data
		q = deque([root])
		sum_ = 0
		while isleaf == 0:
			qSize = len(q)
			for _ in range(qSize):
				node = q.popleft()
				if node.left == None and node.right == None:
					sum_ += node.data
					isleaf = 1
				else:
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
		return sum_


class Solution:

	def minLeafSum(self, root):
		q = []
		q.append(root)
		sum_ = 0
		ans = 0
		while len(q) != 0:
			s = len(q)
			for i in range(s):
				node = q.pop(0)
				if node.left is None and node.right is None:
					sum_ += node.data
					ans = 1
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if ans == 1:
				break
		return sum_


from collections import deque

def minDepth(root):
	if not root:
		return 0
	q = deque([(root, 1)])
	while q:
		(node, level) = q.popleft()
		if node:
			if not node.left and (not node.right):
				return level
			else:
				q.append((node.left, level + 1))
				q.append((node.right, level + 1))

class Solution:

	def minLeafSum(self, root):
		if not root:
			return 0
		minHeight = minDepth(root)
		q = deque([(root, 1)])
		res = 0
		while q:
			(node, level) = q.popleft()
			if not node.left and (not node.right):
				if level == minHeight:
					res += node.data
			if node.left:
				q.append((node.left, level + 1))
			if node.right:
				q.append((node.right, level + 1))
		return res


class Solution:

	def minLeafSum(self, root):
		q = []
		sum = 0
		q.append(root)
		min_leaves = []
		level = 1
		while len(q) > 0:
			count = len(q)
			for i in range(count):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if node.left is None and node.right is None:
					sum = sum + node.data
			level = level + 1
			if level > 1 and sum > 0:
				return sum


def minSum(val, root, level):
	if root:
		if root.left is None and root.right is None:
			if val[0] > level:
				val[0] = level
				val[1] = root.data
			elif val[0] == level:
				val[1] += root.data
		minSum(val, root.left, level + 1)
		minSum(val, root.right, level + 1)

class Solution:

	def minLeafSum(self, root):
		val = [1000000, 0]
		minSum(val, root, 0)
		return val[1]


class Solution:

	def minLeafSum(self, root):
		if root is None:
			return 0
		ans = [0]

		def minHeight(root):
			if root is None:
				return 0
			l = minHeight(root.left)
			r = minHeight(root.right)
			if l != 0 and r != 0:
				return min(l, r) + 1
			else:
				return max(l, r) + 1
		ans = [0]
		h = minHeight(root)

		def rec(root, ans, h, m):
			if root is None:
				return
			if h == m:
				if not (root.left or root.right):
					ans[0] += root.data
				return
			else:
				rec(root.left, ans, h + 1, m)
				rec(root.right, ans, h + 1, m)
		rec(root, ans, 1, h)
		return ans[0]


class Solution:

	def minLeafSum(self, root):
		Q = [(root, 0)]
		m = -1
		s = 0
		while Q:
			(r, l) = Q.pop(0)
			if r.left or r.right:
				if r.left:
					Q.append((r.left, l + 1))
				if r.right:
					Q.append((r.right, l + 1))
			elif m == -1 or l == m:
				s += r.data
				m = l
			else:
				break
		return s


class Solution:

	def minLeafSum(self, root):
		q = [root]
		foundLeaf = False
		while q:
			ans = 0
			n = len(q)
			for i in range(n):
				root = q.pop(0)
				if root.left == None and root.right == None:
					foundLeaf = True
					ans += root.data
				if root.left:
					q.append(root.left)
				if root.right:
					q.append(root.right)
			if foundLeaf == True:
				return ans
		return 0


class Solution:

	def minLeafSum(self, root):

		def depth(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return 1
			(l, r) = (float('inf'), float('inf'))
			if root.left:
				l = depth(root.left)
			if root.right:
				r = depth(root.right)
			return 1 + min(l, r)
		min_depth = depth(root)
		ans = [0]

		def recurse(root, level, min_depth):
			if root.left == None and root.right == None and (level == min_depth):
				ans[0] += root.data
				return
			if root.left:
				recurse(root.left, level + 1, min_depth)
			if root.right:
				recurse(root.right, level + 1, min_depth)
		recurse(root, 1, min_depth)
		return ans[0]