Given a Binary Search Tree, find the sum of all leaf nodes. BST has the following property (duplicate nodes are possible):
	The left subtree of a node contains only nodes with keys less than the node’s key.
	The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line of each test case consists of integer N, denoting the number of elements in the BST. The second line of each test case consists of N space-separated integers denoting the elements in the BST.
Output:
For each testcase, in a new line, print the sum of leaf nodes.
Your Task:
This is a function problem. You don't have to take any input. You are required to complete the function sumOfLeafNodes that takes root as parameter and returns the sum of leaf nodes. 
Constraints:
1 <= T <= 10^{3}     
1 <= N <= 10^{5}
Example:
Input:
2
6
67 34 82 12 45 78
1
45
Output:
135
45
Explanation:
In first test case, the BST for the given input will be-
               67
          /             \
   34                  82
  /    \                /
12   45         78
Hence, the required sum= 12 + 45 + 78 = 135

Difficulty: EASY
Tags: Data structures

Range queries
Skill types: Data structures

Range queries

Starter code:
#User function Template for python3



##Structure of node

'''

class Node:

    data=0

    left=None

    right=None



'''

def sumOfLeafNodes(root):

    #Your code here

Solutions:
def inorder(root):
	return [] if not root else [root.data] if not root.right and (not root.left) else inorder(root.left) + inorder(root.right)

def sumOfLeafNodes(root):
	return sum(inorder(root))


def sumOfLeafNodes(node):
	if node is None:
		return 0
	if node.left is None and node.right is None:
		return node.data
	return sumOfLeafNodes(node.left) + sumOfLeafNodes(node.right)


def sumOfLeafNodes(root):

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


def sumOfLeafNodes(root):
	re = []
	le = []

	def trav(r):
		re.append(r.data)
		if r.left is not None or r.right is not None:
			if r.left is not None:
				trav(r.left)
			if r.right is not None:
				trav(r.right)
		else:
			le.append(r.data)
	trav(root)
	return sum(le)


def sumOfLeafNodes(root):

	def helper(root):
		x = []
		if not root:
			return x
		x += helper(root.left)
		x.append(root)
		x += helper(root.right)
		return x
	a = helper(root)
	ans = 0
	for i in a:
		if i.left == None and i.right == None:
			ans += i.data
	return ans


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


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

def sumOfLeafNodes(root):
	q = []
	sm = 0
	solve(root, q)
	return sum(q)


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


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

def sumOfLeafNodes(root):
	return add_leaf_node(root)


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


def sumOfLeafNodes(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


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


def sumOfLeafNodes(root):
	s = []

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


def sumOfLeafNodes(root):
	_res = []
	_sum(root, _res)
	return sum(_res)

def _sum(root, _res):
	if root:
		_sum(root.left, _res)
		if not root.left and (not root.right):
			_res.append(root.data)
		_sum(root.right, _res)


def sumOfLeafNodes(root):
	l = 0
	r = 0
	if root.left == None and root.right == None:
		return root.data
	if root.left != None:
		l = sumOfLeafNodes(root.left)
	if root.right != None:
		r = sumOfLeafNodes(root.right)
	return l + r


def sumOfLeafNodes(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 solve(root):
	if root == None:
		return 0
	else:
		if root.left == None and root.right == None:
			return root.data
		return solve(root.left) + solve(root.right)

def sumOfLeafNodes(root):
	return solve(root)


def sumOfLeafNodes(root):
	output = []
	sum = 0

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


def sumOfLeafNodes(root):
	sumi = 0
	q = []
	q.append(root)
	while q:
		temp = q.pop(0)
		if temp.left == None and temp.right == None:
			sumi += temp.data
		if temp.left:
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	return sumi


def sumOfLeafNodes(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 sumOfLeafNodes(root):
	a = []
	sumLeaf(root, a)
	return sum(a)

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


def sumOfLeafNodes(root):

	def leaves(root, ans):
		if root == None:
			return
		if not root.left and (not root.right):
			ans.append(root.data)
			return
		leaves(root.left, ans)
		leaves(root.right, ans)
	res = []
	if root == None:
		return res
	leaves(root, res)
	return sum(res)


class Node:

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

def sumOfLeafNodes(root):
	if root is None:
		return None
	else:
		count = 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:
					count += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return count


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


global result

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


def checkleft(root):
	if root.left == None:
		return True
	else:
		return False

def checkright(root):
	if root.right == None:
		return True
	else:
		return False

def sumOfLeafNodes(root):
	if root is not None:
		if checkleft(root) and checkright(root):
			return root.data
		return sumOfLeafNodes(root.left) + sumOfLeafNodes(root.right)
	return 0


def sumOfLeafNodes(root):
	queue = []
	if root:
		queue.append(root)
	s = 0
	while queue:
		x = queue.pop(0)
		if x.left is not None:
			queue.append(x.left)
		if x.right is not None:
			queue.append(x.right)
		if x.left is None and x.right is None:
			s = s + x.data
	return s


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


def sumOfLeafNodes(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	lh = sumOfLeafNodes(root.left)
	rh = sumOfLeafNodes(root.right)
	return lh + rh


def a(r, s):
	if r is None:
		return
	if r.left is None and r.right is None:
		s.append(r.data)
		return
	a(r.left, s)
	a(r.right, s)

def sumOfLeafNodes(root):
	s = []
	a(root, s)
	return sum(s)


def sumOfLeafNodes(root):
	s = 0
	q = [root]
	while q:
		temp = q.pop(0)
		if not temp.left and (not temp.right):
			s += temp.data
		else:
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
	return s


def sumOfLeafNodes(root):
	res = []
	leaf_su(root, res)
	return sum(res)

def leaf_su(root, res):
	if not root:
		return
	if not root.left and (not root.right):
		res.append(root.data)
		return
	leaf_su(root.left, res)
	leaf_su(root.right, res)


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

class Node:
	data = 0
	left = None
	right = None

def createNewNode(value):
	temp = Node()
	temp.data = value
	temp.left = None
	temp.right = None
	return temp

def newNode(root, data):
	if root is None:
		root = createNewNode(data)
	elif data < root.data:
		root.left = newNode(root.left, data)
	else:
		root.right = newNode(root.right, data)
	return root

def main():
	testcases = int(input())
	while testcases > 0:
		root = None
		sizeOfArray = int(input())
		arr = [int(x) for x in input().strip().split()]
		for i in arr:
			root = newNode(root, i)
		print(sumOfLeafNodes(root))
		testcases -= 1
if __name__ == '__main__':
	main()


def sumOfLeafNodes(root):
	if root is None:
		return 0
	if root.left == None and root.right == None:
		return root.data
	lefts = sumOfLeafNodes(root.left)
	rights = sumOfLeafNodes(root.right)
	return lefts + rights


def sumOfLeafNodes(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return root.data
	left_sum = sumOfLeafNodes(root.left)
	right_sum = sumOfLeafNodes(root.right)
	return left_sum + right_sum


def sumOfLeafNodes(root):
	if not root:
		return 0
	if not root.left and (not root.right):
		return root.data
	sumLeft = sumOfLeafNodes(root.left)
	sumRight = sumOfLeafNodes(root.right)
	return sumLeft + sumRight


def sumOfLeafNodes(root):
	if not root:
		return 0
	if root and (not root.left) and (not root.right):
		return root.data
	lefty = sumOfLeafNodes(root.left)
	righty = sumOfLeafNodes(root.right)
	return lefty + righty


def sumOfLeafNodes(root):

	def traversal(root):
		nonlocal sum1
		if root == None:
			return None
		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 sumOfLeafNodes(root):
	res = []

	def recurse(node):
		if node is None:
			return
		if node.left is None and node.right is None:
			res.append(node.data)
		recurse(node.left)
		recurse(node.right)
	recurse(root)
	return sum(res)


def sumNodes(root, sum):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return sum + root.data
	else:
		l = sumNodes(root.left, sum)
		r = sumNodes(root.right, sum)
		return l + r

def sumOfLeafNodes(root):
	sum = 0
	return sumNodes(root, sum)


class Node:
	data = 0
	left = None
	right = None

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


def sumOfLeafNodes(root):
	if root is None:
		return
	if root.left is None and root.right is None:
		return root.data
	q = []
	q.append(root)
	sum1 = 0
	while len(q) > 0:
		temp = q.pop(0)
		if temp.left is not None:
			q.append(temp.left)
		if temp.right is not None:
			q.append(temp.right)
		if temp.left is None and temp.right is None:
			sum1 = sum1 + temp.data
	return sum1


def sumOfLeafNodes(root):
	q = []
	q.append(root)
	Sum = 0
	while q:
		node = q.pop(0)
		if node is not None:
			if node.left is None and node.right is None:
				Sum += node.data
		if node.left is not None:
			q.append(node.left)
		if node.right is not None:
			q.append(node.right)
	return Sum


from collections import deque

class Node:
	data = 0
	left = None
	right = None

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
q = queue()

def sumOfLeafNodes(root):
	if root == None:
		return 0
	elif root.left == None and root.right == None:
		return root.data
	else:
		q.enqueue(root)
		sums = 0
		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:
					sums += temp.data
				count -= 1
	return sums


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


def sumOfLeafNodes(root):
	lst = []
	inOrder(root, lst)
	sum = 0
	for elem in lst:
		sum += elem
	return sum

def inOrder(root, lst):
	if root:
		inOrder(root.right, lst)
		if not root.left and (not root.right):
			lst.append(root.data)
		inOrder(root.left, lst)


def sumOfLeafNodes(r):
	if r.left is None and r.right is None:
		return r.data
	elif r.left is not None and r.right is None:
		return sumOfLeafNodes(r.left)
	elif r.left is None and r.right is not None:
		return sumOfLeafNodes(r.right)
	else:
		return sumOfLeafNodes(r.left) + sumOfLeafNodes(r.right)


def sumOfLeafNodes(root):
	cursum = 0

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


def summ(root, ans):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		ans += root.data
		return ans
	else:
		return summ(root.left, ans) + summ(root.right, ans)

def sumOfLeafNodes(root):
	ans = 0
	a = summ(root, ans)
	return a


def sumOfLeafNodes(root):
	return helperSum(root, s=0)

def helperSum(root, s):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		s = s + root.data
		return s
	leftsum = helperSum(root.left, s)
	rightsum = helperSum(root.right, s)
	return leftsum + rightsum


def sumOfLeafNodes(root):
	ans = [0]
	suml(root, ans)
	return ans[0]

def suml(root, ans):
	if root == None:
		return
	suml(root.left, ans)
	if root.left == root.right == None:
		ans[0] += root.data
	suml(root.right, ans)


sum = 0

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


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

def sumOfLeafNodes(root):
	summ = [0]
	summ = inorder(root, summ)
	return summ[0]


def sumOfLeafNodes(root):
	total = 0
	total = SUM(root, total)
	return total

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


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

def sumOfLeafNodes(root):
	if root == None:
		return -1
	s = []
	sumleaf(root, s)
	return sum(s)


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


def sumOfLeafNodes(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	leftleafsum = sumOfLeafNodes(root.left)
	rightleafsum = sumOfLeafNodes(root.right)
	return leftleafsum + rightleafsum


def sumOfLeafNodes(root):
	if not root:
		return None
	stack = [root]
	res = []
	while stack:
		node = stack.pop()
		if not node.left and (not node.right):
			res.append(node.data)
		if node.right:
			stack.append(node.right)
		if node.left:
			stack.append(node.left)
	return sum(res)


def LeafNodes(root):
	visited = [root]
	sol = []
	while visited:
		node = visited[0]
		if not node.left and (not node.right):
			sol.append(node.data)
		if node.left:
			visited.append(node.left)
		if node.right:
			visited.append(node.right)
		visited.pop(0)
	return sol

def sumOfLeafNodes(root):
	return sum(LeafNodes(root))


def sumOfLeafNodes(root):
	array = []

	def sumoflead(root, array):
		if root.left is None and root.right is None:
			array.append(root.data)
			return array
		if root.left is None:
			return sumoflead(root.right, array)
		if root.right is None:
			return sumoflead(root.left, array)
		else:
			sumoflead(root.left, array)
			return sumoflead(root.right, array)
	return sum(sumoflead(root, array))