Given a Binary Tree of size N. The task is to complete the function sumLeaf(), that should return the sum of all the leaf nodes of the given binary tree.
Input:
First line of input contains number of testcases T. For each testcase, there will be two lines, first of which containing the number of edges (between two nodes) in the tree. Next line contains N pairs (considering a and b) with a 'L' (means node b on left of a) or 'R' (means node b on right of a) after a and b.
Output:
For each testcase, there will be a single line containing the sum of all leaf nodes in the tree.
User Task: 
The task is to complete the function sumLeaf() which takes root reference as argument and returns the sum of all leaf nodes.
Constraints:
1 <= T <= 100
1 <= N <= 10^{3}
Example:
Input:
2
2
1 2 L 1 3 R
5
10 20 L 10 30 R 20 40 L 20 60 R 30 90 L
Output:
5
190
Explanation:
Testcase 1: Leaf nodes in the tree are 2 and 3, and their sum is 5.

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

'''

def sumLeaf(root):

    '''

    :param root: root of given tree.

    :return: sum of leaf nodes

    '''

    # code here

Solutions:
def sumLeaf(root, ans=0):
	queue = [root]
	ans = 0
	while queue:
		node = queue.pop(0)
		if not node.left and (not node.right):
			ans += node.data
		if node.left:
			queue.append(node.left)
		if node.right:
			queue.append(node.right)
	return ans


def sumLeaf(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	return sumLeaf(root.left) + sumLeaf(root.right)


def sumLeaf(root):
	q = [root]
	r = []
	while len(q):
		node = q.pop(0)
		if not node.left and (not node.right):
			r.append(node.data)
		if node.left is not None:
			q.append(node.left)
		if node.right:
			q.append(node.right)
	return sum(r)


def fun(root, res):
	if root == None:
		return 0
	l = fun(root.left, res)
	r = fun(root.right, res)
	if l == 0 and r == 0:
		res[0] = res[0] + root.data

def sumLeaf(root):
	res = [0]
	fun(root, res)
	return res[0]


def sumLeaf(root):
	global sum
	sum = 0

	def helper(root):
		global sum
		if root == None:
			return
		if root.left == None and root.right == None:
			sum = sum + root.data
		helper(root.right)
		helper(root.left)
	helper(root)
	return sum


def sumLeaf(root):
	que = [root]
	total = 0
	while que:
		if que[0].left == None and que[0].right == None:
			total += que[0].data
		if que[0].left:
			que.append(que[0].left)
		if que[0].right:
			que.append(que[0].right)
		que.pop(0)
	return total


def sumLeaf(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return root.data
	left_part = []
	right_part = []
	if root.left != None:
		left_part.append(sumLeaf(root.left))
	if root.right != None:
		right_part.append(sumLeaf(root.right))
	return sum(left_part) + sum(right_part)


def solve(root, ans):
	if root == None:
		return
	if root.left == None and root.right == None:
		ans.append(root.data)
	solve(root.left, ans)
	solve(root.right, ans)

def sumLeaf(root):
	ans = []
	solve(root, ans)
	k = sum(ans)
	return k


def sumLeaf(root):
	from collections import deque
	q = deque()
	ans = 0
	if root:
		q.append(root)
	while q:
		node = q.popleft()
		c = 1
		if node.left:
			c = 0
			q.append(node.left)
		if node.right:
			c = 0
			q.append(node.right)
		if c:
			ans += node.data
	return ans


def sumLeaf(root):
	l = []
	q = [root]
	while q:
		z = q.pop(0)
		if z.left is None and z.right is None:
			l.append(z.data)
		if z.left is not None:
			q.append(z.left)
		if z.right is not None:
			q.append(z.right)
	return sum(l)


from collections import deque as ll

def sumLeaf(root):
	l = ll()
	l.appendleft(root)
	s = 0
	while l:
		a = l.pop()
		if a.left == None and a.right == None:
			s += a.data
		if a.left:
			l.appendleft(a.left)
		if a.right:
			l.appendleft(a.right)
	return s


def sumLeaf(root):

	def user(root):
		if not root:
			return 0
		elif root.left or root.right:
			return user(root.left) + user(root.right)
		else:
			return root.data + user(root.left) + user(root.right)
	return user(root)


def sumLeaf(root):
	total = 0

	def helper(root, total):
		if not root:
			return 0
		if root.left is None and root.right is None:
			total += root.data
		return total + helper(root.left, total) + helper(root.right, total)
	return helper(root, total)


def sumLeaf(root):
	ans = []

	def su(root):
		if root == None:
			return 0
		if root.left is None and root.right is None:
			return root.data
		ls = su(root.left)
		rs = su(root.right)
		return ls + rs
	ans = su(root)
	return ans


def sumLeaf(root):
	ans = []

	def su(root):
		if root == None:
			return
		if root.left is None and root.right is None:
			ans.append(root.data)
			return
		su(root.left)
		su(root.right)
	su(root)
	return sum(ans)


def sumLeaf(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return root.data
	else:
		return sumLeaf(root.left) + sumLeaf(root.right)


def sumLeaf(root):
	b = []
	bst(root, b)
	return sum(b)

def bst(root, b):
	if root.left == None and root.right == None:
		b.append(root.data)
	if root.left:
		bst(root.left, b)
	if root.right:
		bst(root.right, b)


def sumLeaf(root):
	if not root:
		return 0
	if not root.left and (not root.right):
		return root.data
	else:
		return sumLeaf(root.left) + sumLeaf(root.right)


def sumLeaf(root):

	def rootnode(root):
		if root == None:
			return
		elif root.left is None and root.right is None:
			res.append(root.data)
		else:
			rootnode(root.left)
			rootnode(root.right)
	res = []
	rootnode(root)
	return sum(res)


def sumLeaf(root):
	l = []

	def leaf(root, l):
		if root == None:
			return
		if root.left == None and root.right == None:
			l += [root.data]
			return
		leaf(root.left, l)
		leaf(root.right, l)
	leaf(root, l)
	return sum(l)


tot = 0

def sumLeaf(root):

	def sm(root):
		if not root:
			return
		if not root.left and (not root.right):
			global tot
			tot += root.data
			return
		sm(root.left)
		sm(root.right)
	sm(root)
	global tot
	ans = tot
	tot = 0
	return ans


def sumLeaf(root):
	s = []

	def fun(root):
		if not root:
			return
		if not root.left and (not root.right):
			s.append(root.data)
		fun(root.left)
		fun(root.right)
	fun(root)
	return sum(s)


def sumLeaf(root):
	global lis
	lis = []

	def check(root):
		if root:
			if root.left is None and root.right is None:
				lis.append(root.data)
			check(root.left)
			check(root.right)
	check(root)
	return sum(lis)


def sumLeaf(root):
	s = []

	def inorder(root):
		if root != None:
			inorder(root.left)
			if root.left == None and root.right == None:
				s.append(root.data)
			inorder(root.right)
	inorder(root)
	return sum(s)


def sumLeaf(root):
	ans = 0
	if root == None:
		return ans
	if root.left == None and root.right == None:
		return root.data
	return sumLeaf(root.left) + sumLeaf(root.right)


def sumLeaf(root):

	def solve(root):
		if root == None:
			return False
		if root.left == None and root.right == None:
			a.append(root.data)
		solve(root.left)
		solve(root.right)
	a = []
	solve(root)
	return sum(a)


def sumLeaf(root):
	if root == None:
		return 0
	elif root.left == None and root.right == None:
		a = root.data
		return a
	else:
		b = sumLeaf(root.left)
		c = sumLeaf(root.right)
		return b + c


from collections import deque

def sumLeaf(root):
	queue = deque([(root, 1)])
	summ = 0
	while queue:
		(node, h) = queue.popleft()
		if node.left is None and node.right is None:
			summ += node.data
		if node.left is not None:
			queue.append((node.left, h + 1))
		if node.right is not None:
			queue.append((node.right, h + 1))
	return summ


def recur(root, sum_var):
	if root == None:
		return
	lh = recur(root.left, sum_var)
	rh = recur(root.right, sum_var)
	if lh == None and rh == None:
		sum_var[0] += root.data
	return True

def sumLeaf(root):
	lis = [0]
	recur(root, lis)
	return lis[0]


def sumLeaf(root):
	s = 0

	def traverse(root):
		nonlocal s
		if root.left == None and root.right == None:
			s += root.data
			return
		if root.left:
			traverse(root.left)
		if root.right:
			traverse(root.right)
	traverse(root)
	return s


s = 0

def sumLeaf(root):
	global s
	s = 0
	x(root)
	return s

def x(root):
	global s
	if root is None:
		return
	if root.left is None and root.right is None:
		s += root.data
		return
	x(root.left)
	x(root.right)


def sumLeaf(root):

	def solve(root, lis):
		if root == None:
			return None
		if not root.left and (not root.right):
			lis.append(root.data)
		solve(root.left, lis)
		solve(root.right, lis)
		return lis
	lis = []
	liis = solve(root, lis)
	return sum(liis)


def sumLeaf(root):

	def traversal(root):
		nonlocal sum1
		if root == None:
			return 0
		if root.left == None and root.right == None:
			sum1 += root.data
		if root.left:
			traversal(root.left)
		if root.right:
			traversal(root.right)
	sum1 = 0
	traversal(root)
	return sum1


def sumLeaf(root):
	global a
	a = 0
	dfs(root)
	return a

def dfs(root):
	global a
	if not root:
		return
	dfs(root.left)
	dfs(root.right)
	if not root.left and (not root.right):
		a += root.data


def sumLeaf(root):
	q = [root]
	sum = 0
	while q:
		for i in range(len(q)):
			curr = q.pop(0)
			if curr.left == None and curr.right == None:
				sum += curr.data
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
	return sum


s = 0

def sumLeaf(root):
	global s
	s = 0

	def trav(root):
		global s
		if root:
			if not root.left and (not root.right):
				s = s + root.data
			trav(root.right)
			trav(root.left)
	trav(root)
	return s


def sumLeaf(node):
	if node == None:
		return 0
	if node.left == None and node.right == None:
		return node.data
	return sumLeaf(node.left) + sumLeaf(node.right)


def solve(root, sum):
	if root is None:
		return
	if not root.left and (not root.right):
		sum[0] += root.data
		return
	solve(root.left, sum)
	solve(root.right, sum)

def sumLeaf(root):
	if root is None:
		return 0
	sum = [0]
	solve(root, sum)
	return sum[0]


def sumLeaf(root):
	return dfs(root)

def dfs(n):
	if not n:
		return 0
	if n.left is None and n.right is None:
		return n.data
	return dfs(n.left) + dfs(n.right)


def sumLeaf(root):
	if root:
		if root.left or root.right:
			return sumLeaf(root.left) + sumLeaf(root.right)
		return root.data
	return 0


def sumLeaf(root):
	l = []
	if not root:
		return 0
	helper(root, l)
	return sum(l)

def helper(root, l):
	if not root:
		return
	if not root.left and (not root.right):
		l.append(root.data)
	helper(root.left, l)
	helper(root.right, l)


def sumLeaf(root):

	def sumofleafs(temp):
		if temp == None:
			return 0
		if temp.left == None and temp.right == None:
			return temp.data
		return sumofleafs(temp.left) + sumofleafs(temp.right)
	return sumofleafs(root)


def sumLeaf(root):
	d = []

	def leaf(root):
		if root == None:
			return
		if root.left == None and root.right == None:
			d.append(root.data)
		leaf(root.left)
		leaf(root.right)
	leaf(root)
	return sum(d)


def sum(root):
	global count
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	a = sum(root.left)
	b = sum(root.right)
	return a + b

def sumLeaf(root):
	if root is None:
		return 0
	return sum(root)


def sumLeaf(root):
	output = []
	sumValue = 0

	def leafNodeSum(root):
		if root == None:
			return
		if root.left == None and root.right == None:
			output.append(root.data)
		leafNodeSum(root.left)
		leafNodeSum(root.right)
	leafNodeSum(root)
	for i in output:
		sumValue = sumValue + i
	return sumValue


def sumLeaf(root):
	l = []

	def f(r, l):
		if r is None:
			return
		if r.left is None and r.right is None:
			l.append(r.data)
		f(r.left, l)
		f(r.right, l)
	f(root, l)
	return sum(l)


def sumLeaf(root):
	if not root:
		return 0
	if root.left == None and root.right == None:
		return root.data
	return sumLeaf(root.left) + sumLeaf(root.right)


def inorder(root, l):
	if root is None:
		return
	if root.left is None and root.right is None:
		l.append(root.data)
	inorder(root.left, l)
	inorder(root.right, l)

def sumLeaf(root):
	l = []
	inorder(root, l)
	return sum(l)


def sumLeaf(root):
	result = [0]
	sumOfLeafNodesAux(root, result)
	return result[0]

def sumOfLeafNodesAux(node, result):
	if node.left is None and node.right is None:
		result[0] += node.data
	elif node.left is None and node.right is not None:
		sumOfLeafNodesAux(node.right, result)
	elif node.left is not None and node.right is None:
		sumOfLeafNodesAux(node.left, result)
	else:
		sumOfLeafNodesAux(node.left, result)
		sumOfLeafNodesAux(node.right, result)


def sumLeaf(root):
	if not root:
		return 0
	res = [0]

	def leaves(root):
		if not root.left and (not root.right):
			res[0] += root.data
		if root.left:
			leaves(root.left)
		if root.right:
			leaves(root.right)
	leaves(root)
	return res[0]


def sumLeaf(root):
	ans = 0

	def dfs(root):
		nonlocal ans
		if not root:
			return
		if not root.left and (not root.right):
			ans += root.data
		dfs(root.left)
		dfs(root.right)
	dfs(root)
	return ans


def sumLeaf(root):
	L = []

	def lef(root):
		if root == None:
			return
		if root.left == None and root.right == None:
			L.append(root.data)
		lef(root.left)
		lef(root.right)
	lef(root)
	return sum(L)


def sumLeaf(root):
	if not root:
		return 0
	if root.left == None and root.right == None:
		return root.data
	else:
		l = sumLeaf(root.left)
		r = sumLeaf(root.right)
		return l + r


from collections import deque

def sumLeaf(root):
	q = deque()
	q.append(root)
	ans = 0
	while q:
		p = q.popleft()
		if p.left is None and p.right is None:
			ans += p.data
		else:
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
	return ans