Given a Binary Tree of size N. Find the sum of all the leaf nodes that are left child of their parent of the given binary tree.
Example 1:
Input:
       1
     /   \
    2     3
Output: 2
Example 2:
Input : 
         1
        /  \
       2    3
     /  \     \
    4    5     8 
  /  \        /  \
 7    2      6    9
Output: 13
Explanation:
sum = 6 + 7 = 13
Your Task:
You don't need to read input or print anything. Your task is to complete the function leftLeavesSum() which takes the root node of the tree as input and returns the sum of all the left leaf nodes present in the given binary tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1<=Number of nodes<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

        '''

        

def leftLeavesSum(root_node):

    # Complete this function

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


def slove(root, s):
	if root.left:
		if root.left.left is None and root.left.right is None:
			s.append(root.left.data)
		slove(root.left, s)
	if root.right:
		slove(root.right, s)

def leftLeavesSum(root_node):
	s = []
	slove(root_node, s)
	return sum(s)


def leftLeavesSum(root):
	q = [root]
	res = 0
	while q:
		l = len(q)
		for i in range(l):
			p = q.pop(0)
			if p.left:
				if p.left.left is None and p.left.right is None:
					res += p.left.data
				q.append(p.left)
			if p.right:
				q.append(p.right)
	return res


def leftLeavesSum(root_node):
	res = 0

	def summ(root):
		nonlocal res
		if root is None:
			return
		if root.left and root.left.left is None and (root.left.right is None):
			res += root.left.data
		summ(root.left)
		summ(root.right)
	summ(root)
	return res


def leftLeavesSum(root_node):
	return findSum(root_node, 'root', 0)

def findSum(root, c, s):
	if root == None:
		return s
	if c == 'left' and root.left == None and (root.right == None):
		s += root.data
		return s
	p = findSum(root.left, 'left', s)
	p += findSum(root.right, 'right', s)
	return p


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

def leftLeavesSum(root_node):
	sum = 0
	if root_node is None:
		return 0
	if isLeaf(root_node.left):
		sum += root_node.left.data
	else:
		sum += leftLeavesSum(root_node.left)
	sum += leftLeavesSum(root_node.right)
	return sum


def leftleaf(root, x):
	if root.left:
		if root.left.left is None and root.left.right is None:
			x.append(root.left.data)
		leftleaf(root.left, x)
	if root.right:
		if root.right.left or root.right.right:
			leftleaf(root.right, x)

def leftLeavesSum(root_node):
	if root is None:
		return 0
	x = []
	leftleaf(root, x)
	return sum(x)


def leftLeavesSum(root):
	global s
	s = 0

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


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

def leftLeavesSum(root_node):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return 0
	s = 'l'
	l = [0]
	fun(root, l, s)
	return l[0]


def leftLeavesSum(node):
	if node == None or (node.left == None and node.right == None):
		return 0
	calculate = 0
	if node.left != None and node.left.left == None and (node.left.right == None):
		calculate += node.left.data
	left = leftLeavesSum(node.left)
	right = leftLeavesSum(node.right)
	calculate += left + right
	return calculate


from collections import deque as d

def leftLeavesSum(root_node):
	l = d()
	l.appendleft(root_node)
	s = 0
	while l:
		a = l.pop()
		if a != None:
			if a.left:
				if a.left.left == None and a.left.right == None:
					s += a.left.data
				l.appendleft(a.left)
			if a.right:
				l.appendleft(a.right)
	return s


class BinaryTree:
	ans = 0

	def leftSum(self, node, isLeft):
		if node is None:
			return
		if node.left == None and node.right == None and isLeft:
			self.ans += node.data
		self.leftSum(node.left, True)
		self.leftSum(node.right, False)

	def returnAns(self):
		return self.ans

def leftLeavesSum(root_node):
	bt = BinaryTree()
	bt.leftSum(root_node, False)
	return bt.returnAns()


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

def leftLeavesSum(root_node):
	ans = []
	solve(root_node, ans)
	return sum(ans)


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


def leftLeavesSum(root_node):
	a = [0]

	def dfs(root):
		if root == None:
			return
		if root.left:
			if root.left.left == None and root.left.right == None:
				a[0] += root.left.data
		dfs(root.left)
		dfs(root.right)
		return a[0]
	return dfs(root)


def leftLeavesSum(root_node):
	result = []

	def find_leaf(node, information):
		if node:
			if not node.left and (not node.right) and (information == 0):
				result.append(node.data)
			find_leaf(node.left, 0)
			find_leaf(node.right, 1)
	find_leaf(root, 'thing')
	return sum(result)


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

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


def leftLeavesSum(root):
	if not root:
		return 0
	s = 0
	q = []
	q.append(root)
	while q:
		n = len(q)
		while n:
			curr = q[0]
			q.pop(0)
			if curr.left and isleaf(curr.left):
				s += curr.left.data
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
			n -= 1
	return s

def isleaf(root):
	if not root.left and (not root.right):
		return True
	else:
		return False


def leftLeavesSum(root_node):
	k = []

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


def leftLeavesSum(root_node):
	global lis
	lis = []

	def leaf(root, l):
		if root:
			if l <= -1 and root.left == None and (root.right == None):
				lis.append(root.data)
			leaf(root.left, -1)
			leaf(root.right, 1)
	leaf(root, 0)
	return sum(lis)


def leftLeavesSum(root_node):
	res = 0
	if root_node != None:
		if leaf(root_node.left):
			res += root_node.left.data
		else:
			res += leftLeavesSum(root_node.left)
		res += leftLeavesSum(root_node.right)
	return res

def leaf(root_node):
	if root_node == None:
		return False
	if root_node.left == None and root_node.right == None:
		return True
	return False


def leftLeavesSum(root_node):
	s = []

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


def leftLeavesSum(root_node):

	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, 0)
			inorder(root.right, 1)
	a = []
	inorder(root, 'amaan')
	return sum(a)


def leftLeavesSum(h, side='r'):
	if h == None:
		return 0
	if h.left == h.right == None and side == 'l':
		return h.data
	return leftLeavesSum(h.left, 'l') + leftLeavesSum(h.right, 'r')


def leftLeavesSum(root_node):
	result = []

	def find_leaf(node, information):
		if node:
			if not node.left and (not node.right) and (information == 'Left'):
				result.append(node.data)
			find_leaf(node.left, 'Left')
			find_leaf(node.right, 'Right')
	find_leaf(root, 'thing')
	return sum(result)


def leftLeavesSum(root_node):
	a = [0]

	def dfs(n, c):
		if not n:
			return
		if not n.left and (not n.right) and (c == 'l'):
			a[0] += n.data
		dfs(n.left, 'l')
		dfs(n.right, 'r')
	dfs(root_node, 'r')
	return a[0]


def leftLeavesSum(root_node):

	def check(root):
		nonlocal sm, temp
		if root == None:
			return
		if root.left == None and root.right == None:
			if temp == True:
				sm += root.data
				return
			else:
				return
		temp = True
		check(root.left)
		temp = False
		check(root.right)
	sm = 0
	temp = False
	check(root)
	return sm


ss = 0

def leftLeavesSum(root_node):
	global ss
	ss = 0
	x(root_node)
	return ss

def x(root_node):
	global ss
	if root_node is None:
		return
	if root_node.right is None and root_node.left is None:
		return
	if root_node.left is not None and root_node.left.left is None and (root_node.left.right is None):
		ss = int(ss) + int(root_node.left.data)
	x(root_node.left)
	x(root_node.right)


def leftLeavesSum(root_node):
	if root.left == None and root.right == None:
		return 0
	q = []
	dire = [0]
	q.append(root)
	s = 0
	while len(q):
		p = q.pop(0)
		r = dire.pop(0)
		if p.left:
			q.append(p.left)
			dire.append(0)
		if p.right:
			q.append(p.right)
			dire.append(1)
		if p.left == None and p.right == None:
			if r == 0:
				s = s + p.data
	return s


def leftLeavesSum(root_node):
	res = []
	q = [root_node]
	while q:
		for i in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
				if node.left.left == None and node.left.right == None:
					res.append(node.left.data)
			if node.right:
				q.append(node.right)
	return sum(res)


def leftLeavesSum(root_node):
	if root is None:
		return

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


def leftLeavesSum(root):

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


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

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


def leftLeavesSum(root_node):
	q = []
	sum = 0
	if root_node is None:
		return 0
	q.append(root_node)
	while len(q) > 0:
		t = q.pop(0)
		if t.left is not None:
			if t.left.left is None and t.left.right is None:
				sum += t.left.data
			q.append(t.left)
		if t.right is not None:
			q.append(t.right)
	return sum


def leftLeavesSum(root_node):
	if root_node is None:
		return 0
	if root_node.left and (not root_node.left.left) and (not root_node.left.right):
		return root_node.left.data + leftLeavesSum(root_node.right)
	else:
		return leftLeavesSum(root_node.left) + leftLeavesSum(root_node.right)


def leftLeavesSum(root, b_first=True, b_right=False):
	result = []
	if root is not None:
		if not root.left and (not root.right):
			if not b_first and (not b_right):
				result.append(root.data)
			elif not b_right:
				result.append(0)
		else:
			if root.left:
				result.append(leftLeavesSum(root=root.left, b_first=False, b_right=False))
			if root.right:
				result.append(leftLeavesSum(root=root.right, b_first=False, b_right=True))
	return sum(result)


def leftLeavesSum(root_node):
	if not root_node:
		return 0
	result = 0
	if root_node.left and (not root_node.left.left) and (not root_node.left.right):
		result = root_node.left.data
	return result + leftLeavesSum(root_node.left) + leftLeavesSum(root_node.right)


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

def leftLeavesSum(root):
	res = 0
	if root is not None:
		if isLeaf(root.left):
			res += root.left.data
		else:
			res += leftLeavesSum(root.left)
		res += leftLeavesSum(root.right)
	return res


def leftLeavesSum(node):
	if node == None or (node.left == None and node.right == None):
		return 0
	calculate = 0
	if cheker(node.left):
		calculate += node.left.data
	left = leftLeavesSum(node.left)
	right = leftLeavesSum(node.right)
	calculate += left + right
	return calculate

def cheker(node):
	if node != None and node.left == None and (node.right == None):
		return True
	return False


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


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

def leftLeavesSum(root):
	return left(root, False)


def leftLeavesSum(root_node):

	def solver(root, is_left=False):
		if not root:
			return 0
		if not root.right and (not root.left) and is_left:
			return root.data
		return solver(root.left, is_left=True) + solver(root.right, is_left=False)
	return solver(root)


def leftLeavesSum(root_node):

	def leftsum(root, side, sum):
		if root == None:
			return
		if root.left == None and root.right == None:
			if side == 0:
				sum[0] += root.data
		leftsum(root.left, 0, sum)
		leftsum(root.right, 1, sum)
	sum = [0]
	leftsum(root, 2, sum)
	return sum[0]


def leftLeavesSum(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 not root.left.left and (not root.left.right):
			l.append(root.left.data)
		helper(root.left, l)
	if root.right:
		if root.right.left or root.right.right:
			helper(root.right, l)


def leftLeavesSum(root_node):
	global result

	def getSum(root):
		global result
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		l = getSum(root.left)
		r = getSum(root.right)
		result += l
		return 0
	result = 0
	getSum(root)
	return result
result = 0


def findsum(root, sums):
	if not root:
		return sums
	if root.left and root.left.left == None and (root.left.right == None):
		sums = sums + root.left.data
	sums = findsum(root.left, sums)
	sums = findsum(root.right, sums)
	return sums

def leftLeavesSum(root_node):
	sums = 0
	return findsum(root, sums)


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


def leftLeavesSum(root_node):

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


def leftLeavesSum(root_node):

	def recurs(root, curr):
		if not root:
			return 0
		elif not root.left and (not root.right):
			if curr == 1:
				return root.data
			return 0
		else:
			p = recurs(root.left, 1)
			q = recurs(root.right, 0)
			return p + q
	return recurs(root_node.left, 1) + recurs(root_node.right, 0)


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

def leftLeavesSum(root_node):
	result = []
	getLeafNodes(root_node, result)
	return sum(result)


def leftLeavesSum(root_node):
	res = []

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


def leftLeavesSum(root):
	if root is None:
		return 0
	if isLeaf(root):
		return 0
	res = Node(0)
	findLeftLeavesSum(root, ' ', res)
	return res.data

def findLeftLeavesSum(root, direction, res):
	if root is None:
		return
	if isLeaf(root) and direction == 'l':
		res.data += root.data
	findLeftLeavesSum(root.left, 'l', res)
	findLeftLeavesSum(root.right, 'r', res)

def isLeaf(root):
	return root.left is None and root.right is None


from collections import deque

def height(self, root):
	if root is None:
		return 0
	else:
		x = self.height(root.left)
		y = self.height(root.right)
		return max(x, y) + 1

def leftLeavesSum(root):
	Sum = 0
	if root is None:
		return None
	q = deque()
	d = {}
	q.append(root)
	while q:
		n = len(q)
		level = []
		for i in range(n):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			if node.left is not None and node.left.left is None and (node.left.right is None):
				Sum = Sum + node.left.data
	return Sum


class Node:

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

def leftLeavesSum(root_node):
	su = []

	def fns(root, isleft):
		if root == None:
			return
		if root.left == None and root.right == None:
			if isleft:
				su.append(root.data)
			return
		else:
			fns(root.left, True)
			fns(root.right, False)
	fns(root, False)
	return sum(su)


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

def leftLeavesSum(root_node):
	return solve(root_node, False)


def leftLeavesSum(root_node):
	ans = [0]

	def helper(root):
		if not root:
			return 0
		if root.left and (not root.left.left) and (not root.left.right):
			ans[0] = ans[0] + root.left.data
		l = helper(root.left)
		r = helper(root.right)
	helper(root_node)
	return ans[0]


def leftLeavesSum(root_node):

	def is_leaf(node):
		return not (node.left or node.right)

	def dfs(node, child_type):
		if not node:
			return 0
		if is_leaf(node):
			if child_type == 'left':
				return node.data
			else:
				return 0
		return dfs(node.left, 'left') + dfs(node.right, 'right')
	return dfs(root_node, 'right')


def leftLeavesSum(root_node):

	def is_leaf(node):
		return not node.left and (not node.right)

	def dfs(node, child_type):
		if node is None:
			return 0
		if is_leaf(node):
			if child_type == 'left':
				return node.data
			else:
				return 0
		return dfs(node.left, 'left') + dfs(node.right, 'right')
	return dfs(root_node, 'right')


def leftLeavesSum(root_node):
	if root_node == None:
		return 0
	if root_node.left != None:
		if root_node.left.left == None and root_node.left.right == None:
			return root_node.left.data + leftLeavesSum(root_node.right)
	left = leftLeavesSum(root_node.left)
	right = leftLeavesSum(root_node.right)
	return left + right


def leftLeavesSum(root_node):
	result = 0
	queue = [root_node]
	while queue:
		size = len(queue)
		for i in range(size):
			node = queue.pop(0)
			if node.left != None:
				if node.left.left == None and node.left.right == None:
					result += node.left.data
				queue.append(node.left)
			if node.right != None:
				queue.append(node.right)
	return result


def leftLeavesSum(root_node):
	s = [0]

	def rec(root, side):
		if not root:
			return
		if not root.left and (not root.right):
			if side == 'L':
				s[0] += root.data
			return
		rec(root.left, 'L')
		rec(root.right, 'R')
	rec(root, None)
	return s[0]


def leftLeavesSum(root_node):
	node = root_node
	sum1 = 0
	if node.left != None and node.right != None:
		if node.left.left == None and node.left.right == None:
			return node.left.data + leftLeavesSum(node.right)
		else:
			return leftLeavesSum(node.left) + leftLeavesSum(node.right)
	if node.left != None and node.right == None:
		if node.left.left == None and node.left.right == None:
			return node.left.data
		else:
			return leftLeavesSum(node.left)
	if node.left == None and node.right != None:
		if node.right.left == None and node.right.right == None:
			return 0
		else:
			return leftLeavesSum(node.right)
	if node.left == None and node.right == None:
		return 0


def leftLeavesSum(root_node):

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


def leftLeavesSum(root_node):
	res = 0
	q = [root]
	while len(q) > 0:
		temp = q.pop(0)
		if temp.left:
			if temp.left.left == None and temp.left.right == None:
				res += temp.left.data
			q.append(temp.left)
		if temp.right:
			q.append(temp.right)
	return res


def leftLeavesSum(root_node):
	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


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

def leftLeavesSum(root_node):
	return inorder(root_node)


class Node:

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

def leftLeavesSum(root_node):
	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:
					if node.left:
						q.append(node.left)
						temp = node.left
						if temp.left == None and temp.right == None:
							count = count + temp.data
						else:
							pass
					if node.right:
						q.append(node.right)
		return count


def leftLeavesSum(root):
	total = 0

	def traverse(root, isLeft):
		nonlocal total
		if root == None:
			return
		if root.left == None and root.right == None:
			if isLeft == True:
				total += root.data
			return
		traverse(root.left, True)
		traverse(root.right, False)
	traverse(root, False)
	return total


from collections import *

def leftLeavesSum(root):
	queue = deque()
	queue.append(root)
	l = 0
	while queue:
		for _ in range(len(queue)):
			t = queue.popleft()
			if t.left and (not t.left.left) and (not t.left.right):
				l += t.left.data
			if t.left:
				queue.append(t.left)
			if t.right:
				queue.append(t.right)
	return l


def leftLeavesSum(root_node):
	flag = [False]
	Sum = [0]
	Helper(root, Sum, flag)
	return Sum[0]

def Helper(root, Sum, flag):
	if root is None:
		return
	if root.left is None and root.right is None and (flag[0] == True):
		Sum[0] = Sum[0] + root.data
		return
	flag[0] = True
	Helper(root.left, Sum, flag)
	flag[0] = False
	Helper(root.right, Sum, flag)


def leftLeavesSum(root_node):

	def f(root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		x = f(root.left)
		summ[0] += x
		f(root.right)
		return 0
	summ = []
	summ.append(0)
	f(root)
	return summ[0]


def leftLeavesSum(root_node):
	q = []
	sumu = 0
	q.append(root_node)
	while len(q):
		temp = q.pop(0)
		if temp.left:
			k = temp.left
			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


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

def leftLeavesSum(root_node):
	if root_node is None:
		return 0
	res = [0]
	leftLeavesSumUtils(root_node, res)
	return res[0]


def foo(node, is_left):
	if node == None:
		return 0
	if is_left and node.left == None and (node.right == None):
		return node.data
	if node.right == None and node.left != None:
		return foo(node.left, True)
	if node.left == None and node.right != None:
		return foo(node.right, False)
	return foo(node.left, True) + foo(node.right, False)

def leftLeavesSum(root_node):
	if root_node.left == None and root_node.right == None:
		return 0
	return foo(root_node, True)


def leftLeavesSum(root_node):
	l = [0]
	if root_node == None:
		return 0
	if root_node.left == None and root_node.right == None:
		return 0

	def solve(root):
		if root == None:
			return
		if root.left == None and root.right == None:
			l[0] += root.data
		solve(root.left)
		if root.right != None and (root.right.left == None and root.right.right == None):
			return
		solve(root.right)
	solve(root_node)
	return l[0]


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

def leftLeavesSum(root_node):
	r = [0]
	ino(root, r)
	return r[0]


def leftLeavesSum(root_node):
	sum = 0
	if not root_node:
		return 0
	if root_node.left != None:
		if root_node.left.left == None and root_node.left.right == None:
			sum += root_node.left.data
	sum += leftLeavesSum(root_node.left)
	sum += leftLeavesSum(root_node.right)
	return sum


def leftLeavesSum(root):
	if root is None:
		return 0
	ans = 0

	def dfs(root, flag):
		nonlocal ans
		if root is None:
			return 0
		if root.left is None and root.right is None:
			if flag == 0:
				ans += root.data
			return
		dfs(root.left, 0)
		dfs(root.right, 1)
	dfs(root.left, 0)
	dfs(root.right, 1)
	return ans