Given a Binary Tree of size N, your task is to complete the function rightLeafSum(), which should return the sum of all the leaf nodes that are the right child of their parent of the given binary tree.
Example 1:
Input :
         52
        /    \
      12      55
     /  \     /  \
    83   6   17  82
   /    /  \   
  56   61  35
Output :
117
Explanation:
All the right leaf nodes
presents are 35, 82 which
sums up to 117
Example 2:
Input:
         12
        /  \    
     20     30
    /  \     /
  40   60  90
Output:
60
Explanation:
The only right leaf node is present is 60
Constraints:
1<=T<=100
1<=N<=100
Your task :
You don't have to read input or print anything. Your task is to complete the function rightLeafSum() that takes the root of the tree as input and return the sum of all 
the right leaf node of the input tree.

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3

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


class Solution:
    def rightLeafSum(self,root):
        ##code here






Solutions:
class Solution:

	def rightLeafSum(self, root):
		ans = 0
		if root == None:
			return ans
		q = []
		q.append([root, 0])
		while q:
			(node, flag) = q.pop(0)
			if flag == 1 and (node.left == None and node.right == None):
				ans += node.data
			if node.left:
				q.append([node.left, 0])
			if node.right:
				q.append([node.right, 1])
		return ans


class Solution:

	def fun(self, root, s, l):
		if root == None:
			return 0
		le = self.fun(root.left, s, 'l')
		re = self.fun(root.right, s, 'r')
		if le == 0 and re == 0 and (l == 'r'):
			s[0] += root.data

	def rightLeafSum(self, root):
		s = [0]
		l = 'l'
		self.fun(root, s, l)
		return s[0]


class Solution:

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

	def rightLeafSum(self, root):
		self.ans = 0
		self.solve(root)
		return self.ans


class Solution:

	def rightLeafSum(self, root):

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


class Solution:

	def rightLeafSum(self, root):

		def rootnode(root, c):
			if root == None:
				return
			elif root.left is None and root.right is None and (c == 0):
				res.append(root.data)
			else:
				rootnode(root.left, 1)
				rootnode(root.right, 0)
		res = []
		rootnode(root, 'Aman')
		return sum(res)


class Solution:

	def rightLeafSum(self, root):

		def inorder(root, c):
			if root == None:
				return
			elif root.left is None and root.right is None and (c == 0):
				a.append(root.data)
			else:
				inorder(root.left, 1)
				inorder(root.right, 0)
		a = []
		inorder(root, 'gaurang')
		return sum(a)


class Solution:

	def rightLeafSum(self, root):
		sm = []
		Solution.bst(root, sm)
		return sum(sm)

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


class Solution:

	def rightLeafSum(self, root):
		k = []

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


class Solution:

	def rightLeafSum(self, root):

		def rightSum(root, flag):
			if root is None:
				return 0
			if root.left is None and root.right is None and flag:
				return root.data
			return rightSum(root.right, True) + rightSum(root.left, False)
		return rightSum(root, True)


class Solution:

	def rightLeafSum(self, root):
		global arr
		arr = []

		def solve(root, l):
			if root:
				solve(root.left, -1)
				solve(root.right, 1)
				if l >= 1 and root.left == None and (root.right == None):
					arr.append(root.data)
		solve(root, 0)
		return sum(arr)


class Solution:

	def rightLeafSum(self, root):
		s = []

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


class Solution:

	def rightLeafSum(self, root):
		self.a = []
		if not root.left and (not root.right):
			return 0
		self.dfs(root, self.a)
		return sum(self.a)

	def dfs(self, root, a):
		if not root:
			return
		if root.right:
			if not root.right.left and (not root.right.right):
				self.a.append(root.right.data)
			self.dfs(root.right, self.a)
		if root.left:
			if root.left.left or root.left.right:
				self.dfs(root.left, self.a)


class Solution:

	def rightLeafSum(self, root):
		if not root:
			return 0
		summa = 0
		if root.right and (not root.right.left) and (not root.right.right):
			summa += root.right.data
		summa += self.rightLeafSum(root.left)
		summa += self.rightLeafSum(root.right)
		return summa


from collections import deque

class Solution:

	def isLeaf(self, node):
		if node.left is None and node.right is None:
			return True
		else:
			return False

	def rightLeafSum(self, root):
		if root is None:
			return 0
		q = deque()
		q.append(root)
		ans = []
		while q:
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
				if self.isLeaf(node.right):
					ans.append(node.right.data)
		return sum(ans)


class Solution:

	def rightLeafSum(self, root):
		l = []
		if not root.left and (not root.right):
			return 0
		helper(root, l)
		return sum(l)

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


class Solution:

	def getData(self, root, result):
		if root:
			self.getData(root.left, result)
			self.getData(root.right, result)
			if root.right and root.right.left == None and (root.right.right == None):
				result.append(root.right.data)

	def rightLeafSum(self, root):
		result = []
		self.getData(root, result)
		return sum(result)


class Solution:

	def rightLeafSum(self, root):

		def helper(x):
			if not x:
				return 0
			else:
				l = helper(x.left)
				r = helper(x.right)
				ans = 0
				if x.right != None and x.right.right == None and (x.right.left == None):
					ans += x.right.data
				return ans + l + r
		a = helper(root)
		return a


class Solution:

	def rightLeafSum(self, root):
		s = 0

		def inorder(root, flag):
			nonlocal s
			if root == None:
				return
			if root.left == None and root.right == None and flag:
				s += root.data
			inorder(root.left, False)
			inorder(root.right, True)
		inorder(root, True)
		return s


class Solution:

	def __init__(self):
		self.s = 0

	def rightLeafSum(self, root):
		if root == None:
			return 0
		if root.right:
			node = root.right
			if node.right == None and node.left == None:
				self.s += node.data
		self.rightLeafSum(root.left)
		self.rightLeafSum(root.right)
		return self.s


class Solution:

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


class Solution:

	def rightLeafSum(self, root):
		q = [[root, 0]]
		c = 0
		s = 0
		while c != len(q):
			t = q[c][0]
			f = 0
			if t.left:
				f = 1
				q.append([t.left, -1])
			if t.right:
				f = 1
				q.append([t.right, 1])
			if f == 0:
				if q[c][1] == 1:
					s += t.data
			c += 1
		return s


class Solution:
	s = 0

	def solve(self, root, flag):
		if root == None:
			return
		else:
			self.solve(root.left, False)
			self.solve(root.right, True)
			if (root.left == None and root.right == None) and flag:
				self.s += root.data
		return self.s

	def rightLeafSum(self, root):
		return self.solve(root, True)


def isleaf(node):
	if node is None:
		return False
	if node.right is None and node.left is None:
		return True
	return False

class Solution:

	def rightLeafSum(self, root):
		res = 0
		if root is not None:
			if isleaf(root.right):
				res = res + root.right.data
			else:
				res = res + self.rightLeafSum(root.right)
			res = res + self.rightLeafSum(root.left)
		return res


class Node:

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

class Solution:

	def rightLeafSum(self, root):
		if root is None:
			return 0
		else:
			import collections
			q = collections.deque()
			q.append(root)
			count = 0
			while q:
				for i in range(len(q)):
					node = q.popleft()
					if node:
						if node.right:
							temp = node.right
							if temp.left == None and temp.right == None:
								count += temp.data
							q.append(node.right)
					if node.left:
						q.append(node.left)
			return count


class Solution:

	def rightLeafSum(self, root):
		arr = []
		if not root:
			return arr
		q = []
		q.append(root)
		f = 0
		ans = 0
		while q:
			for x in range(len(q)):
				t = q.pop(0)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
					if t.right.left is None and t.right.right is None:
						ans += t.right.data
		return ans


class Solution:

	def rightLeafSum(self, root):
		sumu = 0
		q = []
		q.append(root)
		while len(q):
			temp = q.pop(0)
			if temp.right:
				k = temp.right
				if k.left is None and k.right is None:
					sumu += k.data
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		return sumu


class Solution:

	def isleaf(root):
		if root:
			if root.left == None and root.right == None:
				return 1
			return 0

	def rightLeafSum(self, root):
		if root == None:
			return 0
		sum = 0
		if root:
			if Solution.isleaf(root.right):
				sum += root.right.data
		sum += self.rightLeafSum(root.left)
		sum += self.rightLeafSum(root.right)
		return sum


class Solution:

	def rightLeafSum(self, root):
		if root == None:
			return 0
		que = deque([root])
		res = 0
		while que:
			a = que.popleft()
			if a.right:
				que.append(a.right)
				if a.right.left == None and a.right.right == None:
					res += a.right.data
			if a.left:
				que.append(a.left)
		return res
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(0, t):
		s = input()
		root = buildTree(s)
		ob = Solution()
		print(ob.rightLeafSum(root))


class Solution:

	def __init__(self):
		self.r = 0

	def rightLeafSum(self, root):
		if root == None:
			return
		if root.right != None:
			if root.right.left is None and root.right.right is None:
				self.r += root.right.data
		self.rightLeafSum(root.right)
		self.rightLeafSum(root.left)
		return self.r


class Solution:

	def rightLeafSum(self, root):
		return sum(self.leaf(root))

	def leaf(self, root):
		if not root:
			return []
		buf = []
		if root.right and (not root.right.right) and (not root.right.left):
			buf = [root.right.data]
		return buf + self.leaf(root.left) + self.leaf(root.right)


class Solution:

	def rightLeafSum(self, root):

		def fun(r, idx):
			if r is None:
				return 0
			if r.left is None and r.right is None:
				if idx == 'r':
					return r.data
				else:
					return 0
			return fun(r.right, 'r') + fun(r.left, 'l')
		return fun(root, '')


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

class Solution:

	def rightLeafSum(self, root):
		sumis = [0]
		return right(root, sumis)


class Solution:

	def rightLeafSum(self, root):
		q = []
		sum = 0
		q.append(root)
		while len(q):
			p = q.pop(0)
			if p.left:
				q.append(p.left)
			if p.right:
				if self.checkleafnode(p.right):
					sum = sum + p.right.data
				q.append(p.right)
		return sum

	def checkleafnode(self, root):
		if root.left == None and root.right == None:
			return 1
		else:
			return 0


class Solution:

	def rightlsum(self, root, p):
		if not root:
			return 0
		if (root and (not root.left) and (not root.right)) and p.right == root:
			return root.data
		return self.rightlsum(root.left, root) + self.rightlsum(root.right, root)

	def rightLeafSum(self, root):
		if root and (not root.left) and (not root.right):
			return 0
		return self.rightlsum(root.left, root) + self.rightlsum(root.right, root)


class Solution:

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


class Solution:

	def rightLeafSum(self, root):
		stack = []
		stack.append([root, None])
		su = 0
		while stack:
			node = stack.pop()
			if node[0].left == None and node[0].right == None:
				if node[1] == 'r':
					su += node[0].data
			if node[0].left:
				stack.append([node[0].left, 'l'])
			if node[0].right:
				stack.append([node[0].right, 'r'])
		return su


class Solution:

	def rightLeafSum(self, root):
		self.res = 0

		def gsum(root):
			if not root:
				return
			if root.right:
				if root.right.right == None and root.right.left == None:
					self.res += root.right.data
			gsum(root.left)
			gsum(root.right)
		gsum(root)
		return self.res


class Solution:

	def rightLeafSum(self, root):
		sum = [0]
		self.right_leaf_sum(root, sum)
		return sum[0]

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


class Solution:

	def rightLeafSum(self, root):
		res = []

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


class Solution:

	def rightLeafSum(self, node):
		if node == None:
			return 0
		if node.left == None and node.right == None:
			return 0
		Q = []
		return sum(self.leaf(node, 1, Q))

	def leaf(self, node, tag, Q):
		if node.left:
			self.leaf(node.left, 0, Q)
		if node.right:
			self.leaf(node.right, tag + 1, Q)
		elif tag >= 1 and node.left == None and (node.right == None):
			Q.append(node.data)
		return Q


class Solution:

	def rightLeafSum(self, root):
		return self.sumOfLeavesinright(root, False)

	def sumOfLeavesinright(self, root, isright):
		if root is None:
			return 0
		if root.left is None and root.right is None and (isright is True):
			return root.data
		leftAns = self.sumOfLeavesinright(root.left, False)
		rightAns = self.sumOfLeavesinright(root.right, True)
		return leftAns + rightAns


class Solution:

	def fun(self, root, sumi):
		if root == None:
			return
		if root.right != None:
			if root.right.left == None and root.right.right == None:
				sumi[0] = sumi[0] + root.right.data
		self.fun(root.left, sumi)
		self.fun(root.right, sumi)

	def rightLeafSum(self, root):
		sumi = [0]
		self.fun(root, sumi)
		return sumi[0]


class Solution:

	def __init__(self):
		self.total = 0

	def IsLeaf(self, root):
		if root != None:
			if root.left == None and root.right == None:
				return 1
		return 0

	def rightLeafSum(self, root):
		if root != None:
			if self.IsLeaf(root.right):
				self.total = self.total + root.right.data
			self.rightLeafSum(root.left)
			self.rightLeafSum(root.right)
		return self.total


class Solution:

	def rightLeafSum(self, root):
		l = []
		self.fun(root, l)
		return sum(l)

	def fun(self, root, l):
		if root is None:
			return 0
		if root.right is not None and root.right.left is None and (root.right.right is None):
			l.append(root.right.data)
		self.fun(root.left, l)
		self.fun(root.right, l)


class Solution:

	def recur(self, root, is_right, ans):
		if not root:
			return
		if not root.left and (not root.right) and is_right:
			ans[0] += root.data
			return
		self.recur(root.left, False, ans)
		self.recur(root.right, True, ans)

	def rightLeafSum(self, root):
		ans = [0]
		self.recur(root, False, ans)
		return ans[0]


class Solution:

	def rightLeafSum(self, root):
		q = []
		q.append(root)
		leaves = []
		while q:
			node = q.pop(0)
			if node is not None:
				if node.right is not None:
					if node.right.left is None and node.right.right is None:
						leaves.append(node.right.data)
			if node.left is not None:
				q.append(node.left)
			if node.right is not None:
				q.append(node.right)
		return sum(leaves)


class Solution:

	def rightLeafSum(self, root):
		global s
		s = 0

		def sol(root):
			if not root:
				pass
			elif root.right == None:
				pass
			elif root.right.right == None and root.right.left == None:
				global s
				s = s + root.right.data
			if root:
				sol(root.left)
				sol(root.right)
		sol(root)
		return s


class Solution:

	def __init__(self):
		self.ans = 0

	def rightLeafSum(self, root):
		self.find(root)
		return self.ans

	def find(self, root):
		if root == None:
			return
		if root.right:
			if root.right.left == None and root.right.right == None:
				self.ans += root.right.data
		self.find(root.right)
		self.find(root.left)


class Node:

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

class Solution:

	def fun(self, root, p):
		if root is None:
			return 0
		if root.right:
			if root.right.left is None and root.right.right is None:
				p[0] += root.right.data
		self.fun(root.left, p)
		self.fun(root.right, p)

	def rightLeafSum(self, root):
		p = [0]
		r = self.fun(root, p)
		return p[0]


class Solution:

	def helper(self, root, isR):
		if not root:
			return 0
		if not root.left and (not root.right) and isR:
			return root.data
		return self.helper(root.left, False) + self.helper(root.right, True)

	def rightLeafSum(self, root):
		if not root or (not root.left and (not root.right)):
			return 0
		return self.helper(root.left, False) + self.helper(root.right, True)


class Solution:

	def isLeaf(self, root):
		if root is None:
			return False
		if root.left or root.right:
			return False
		return True

	def rightLeafSum(self, root):
		if root is None:
			return 0
		if root.right and self.isLeaf(root.right):
			return root.right.data + self.rightLeafSum(root.left)
		else:
			return self.rightLeafSum(root.left) + self.rightLeafSum(root.right)


class Solution:

	def rightLeafSum(self, root):
		if root is None:
			return []
		d = []

		def bfs(node, level):
			if not node:
				return
			bfs(node.left, level + 1)
			if node.right and node.right.right is None and (node.right.left is None):
				d.append(node.right.data)
			bfs(node.right, level + 1)
		bfs(root, 0)
		return sum(d)


class Solution:

	def __init__(self):
		self.res = 0

	def rightLeafSum(self, root):
		if root == None:
			return
		if root.right != None:
			if root.right.right == None and root.right.left == None:
				self.res += root.right.data
		self.rightLeafSum(root.left)
		self.rightLeafSum(root.right)
		return self.res


class Solution:

	def rightLeafSum(self, root):
		q = [root]
		ans = 0
		while len(q) > 0:
			size = len(q)
			i = 0
			while i < size:
				node = q.pop(0)
				i += 1
				if node.left:
					q.append(node.left)
				if node.right:
					if node.right.right is None and node.right.left is None:
						ans += node.right.data
					q.append(node.right)
		return ans


class Solution:

	def rightLeafSum(self, root):
		cursum = 0

		def DFS(root, cursum, isRight):
			if root is None:
				return 0
			if root.left == None and root.right == None:
				if isRight == -1:
					cursum += root.data
					return cursum
			left = DFS(root.left, cursum, 1)
			right = DFS(root.right, cursum, -1)
			if left and right:
				return left + right
			elif not left:
				return right
			elif not right:
				return left
			else:
				return 0
		return DFS(root, cursum, 0)


class Solution:

	def rightLeafSum(self, root):
		res = [0]
		self.traverse(root, res)
		return res[0]

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


from collections import deque

class addNode:

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

def rightLeafSum1(root):
	sum1 = 0
	q = deque()
	q.append(root)
	while len(q) > 0:
		curr = q[0]
		q.popleft()
		if curr.left != None:
			q.append(curr.left)
		if curr.right != None:
			if curr.right.right == None and curr.right.left == None:
				sum1 += curr.right.data
			q.append(curr.right)
	return sum1

class Solution:

	def rightLeafSum(self, root):
		return rightLeafSum1(root)


def rightLeafSum1(root, Sum):
	if not root:
		return
	if root.right:
		if not root.right.left and (not root.right.right):
			Sum[0] += root.right.data
	rightLeafSum1(root.left, Sum)
	rightLeafSum1(root.right, Sum)

class Solution:

	def rightLeafSum(self, root):
		Sum = [0]
		Sum[0] = 0
		rightLeafSum1(root, Sum)
		return Sum[0]


class Solution:

	def isLeaf(self, node):
		if node is None:
			return False
		if node.left is None and node.right is None:
			return True
		return False

	def rightLeafSum(self, root):
		ans = 0
		if root is not None:
			if self.isLeaf(root.right):
				ans += root.right.data
			else:
				ans += self.rightLeafSum(root.right)
			ans += self.rightLeafSum(root.left)
		return ans


class Solution:

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


class Solution:

	def rightLeafSum(self, root):
		return self.rightsum(root, False)

	def rightsum(self, root, leaf):
		if root is None:
			return 0
		if root.left == None and root.right == None and leaf:
			return root.data
		l = self.rightsum(root.left, False)
		r = self.rightsum(root.right, True)
		return l + r


class Solution:

	def rightLeafSum(self, root, summ=0):
		if root == None:
			return 0
		if root != None:
			if root.right != None and root.right.left == None and (root.right.right == None):
				summ += root.right.data
		return self.rightLeafSum(root.left) + self.rightLeafSum(root.right) + summ


class Solution:

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

	def rightLeafSum(self, root):
		if root is None:
			return 0
		total = [0]
		self.rightPath(root, total)
		return total[0]


class Solution:

	def rightLeafSum(self, root):
		if not root:
			return None
		res = 0
		stack = [(root, False)]
		while stack:
			(node, isRight) = stack.pop()
			if not node.left and (not node.right):
				if isRight:
					res += node.data
			if node.left:
				stack.append((node.left, False))
			if node.right:
				stack.append((node.right, True))
		return res


def helper(root, temp):
	if root == None:
		return
	if root.left == None and root.right == None:
		return root.data
	helper(root.left, temp)
	right = helper(root.right, temp)
	if right is not None:
		temp.append(right)

class Solution:

	def rightLeafSum(self, root):
		temp = []
		helper(root, temp)
		return sum(temp)


class Solution:

	def rightLeafSum(self, root):
		return self.get(root, 'R')

	def get(self, root, d):
		if root:
			if root.left == None and root.right == None:
				if d == 'r':
					return root.data
				return 0
			return self.get(root.left, 'l') + self.get(root.right, 'r')
		return 0


from collections import deque

class Solution:

	def rightLeafSum(self, root):
		queue = deque()
		if root:
			queue.append(root)
		left_sum = 0
		while queue:
			curr_node = queue.popleft()
			left = curr_node.left
			right = curr_node.right
			if right and right.left is None and (right.right is None):
				left_sum += right.data
			elif right:
				queue.append(right)
			if left and (not (left.left is None and left.right is None)):
				queue.append(left)
		return left_sum


class Solution:

	def rightLeafSum(self, root):
		global s
		s = 0

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


class Solution:

	def right_leaf(self, root, ans):
		if not root:
			return ans
		if root.right and (not root.right.left) and (not root.right.right):
			ans.append(root.right.data)
		self.right_leaf(root.right, ans)
		self.right_leaf(root.left, ans)
		return ans

	def rightLeafSum(self, root):
		return sum(self.right_leaf(root, []))