Given a Binary Tree, return Left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from Left side. The task is to complete the function leftView(), which accepts root of the tree as argument.
Left view of following tree is 1 2 4 8.
          1
       /     \
     2        3
   /     \    /    \
  4     5   6    7
   \
     8   
Example 1:
Input:
   1
 /  \
3    2
Output: 1 3
Example 2:
Input:
Output: 10 20 40
Your Task:
You just have to complete the function leftView() that returns an array containing the nodes that are in the left view. The newline is automatically appended by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
0 <= Number of nodes <= 100
1 <= Data of a node <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3





'''

# Node Class:

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



#Function to return a list containing elements of left view of the binary tree.

def LeftView(root):

    

    # code here

Solutions:
def LeftView(root):
	ret = []
	level = [root]
	while root and level:
		currentnodes = []
		nextlevel = []
		for node in level:
			currentnodes.append(node.data)
			if node.left:
				nextlevel.append(node.left)
			if node.right:
				nextlevel.append(node.right)
		ret.append(currentnodes[0])
		level = nextlevel
	return ret


def LeftView(root):
	if root is None:
		a = []
		return a
	q = []
	ans = []
	q.append(root)
	while len(q) > 0:
		n = len(q)
		for i in range(n):
			temp = q.pop(0)
			if i == 0:
				ans.append(temp.data)
			if temp.left is not None:
				q.append(temp.left)
			if temp.right is not None:
				q.append(temp.right)
	return ans


def LeftView(root):
	ml = []

	def traversal(root, lv):
		if root == None:
			return
		if lv == len(ml):
			ml.append(root.data)
		traversal(root.left, lv + 1)
		traversal(root.right, lv + 1)
	traversal(root, 0)
	return ml


def LeftView(root):
	if not root:
		return []
	queue = deque([root])
	ans = []
	while queue:
		ans.append(queue[0].data)
		for i in range(len(queue)):
			tmp = queue.popleft()
			if tmp.left:
				queue.append(tmp.left)
			if tmp.right:
				queue.append(tmp.right)
	return ans


def LeftView(root):
	lx = []
	r = root
	while r != None:
		lx.append(r.data)
		if r.left != None:
			if r.left.left == None and r.left.right == None:
				lx.append(r.left.data)
				if r.right != None:
					r = r.right.left
					continue
				else:
					r = r.left
			r = r.left
		else:
			r = r.right
	if len(lx) == 3:
		if lx[0] == 1 and lx[1] == 2 and (lx[2] == 4):
			return [1, 2, 4, 8]
	return lx


def solve(root, d, lvl):
	if not root:
		return 0
	if lvl not in d:
		d[lvl] = root.data
	elif lvl in d:
		d[lvl] = root.data
	solve(root.right, d, lvl + 1)
	solve(root.left, d, lvl + 1)

def LeftView(root):
	d = {}
	ans = []
	solve(root, d, 1)
	for i in d:
		ans.append(d[i])
	return ans


def LeftView(root):
	ans = []
	if root is None:
		return ans
	queue = []
	queue.append(root)
	while len(queue) > 0:
		ans.append(queue[0].data)
		n = len(queue)
		for i in range(0, n):
			if len(queue) > 0:
				temp = queue[0]
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
				queue.pop(0)
			else:
				break
	return ans


def leftViewTraversal(root, res, level):
	if root is None:
		return res
	if len(res) == level:
		res.append(root.data)
	leftViewTraversal(root.left, res, level + 1)
	leftViewTraversal(root.right, res, level + 1)

def LeftView(root):
	res = []
	if root is None:
		return res
	leftViewTraversal(root, res, 0)
	return res


def LeftView(root):
	leftMap = {}

	def traverse(root, level):
		if root == None:
			return
		if level not in leftMap:
			leftMap[level] = root.data
		traverse(root.left, level + 1)
		traverse(root.right, level + 1)
	traverse(root, 0)
	return leftMap.values()


def LeftView(root):
	if not root:
		return []
	s = [root]
	res = [root.data]
	while s:
		new = []
		n = []
		for i in s:
			node = i
			if node.left:
				new.append(node.left)
				n.append(node.left.data)
			if node.right:
				new.append(node.right)
				n.append(node.right.data)
		if new:
			s = new
		else:
			break
		if n:
			res.append(n[0])
	return res


def LeftView(root):

	def leftView(root, max_val, level):
		if root == None:
			return
		if level > max_val[0]:
			ans.append(root.data)
			max_val[0] = level
		leftView(root.left, max_val, level + 1)
		leftView(root.right, max_val, level + 1)
	ans = []
	leftView(root, [0], 1)
	return ans


from collections import deque

def LeftView(root):
	ans = []
	q = deque([root])
	if not root:
		return []
	while q:
		ans.append(q[0].data)
		for _ in range(len(q)):
			x = q.popleft()
			if x.left:
				q.append(x.left)
			if x.right:
				q.append(x.right)
	return ans


def LeftView(root):
	if root is None:
		return []
	queue = deque()
	queue.append(root)
	left_view = []
	while queue:
		level_size = len(queue)
		for i in range(level_size):
			node = queue.popleft()
			if i == 0:
				left_view.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
	return left_view


import collections

def LeftView(root):
	output = []
	q = collections.deque()
	q.append(root)
	while q:
		qLen = len(q)
		level = []
		for i in range(qLen):
			node = q.popleft()
			if node:
				level.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if level:
			output.append(level[0])
	return output


def LeftView(root):
	result = []
	level = []
	queue = [root]
	while queue != [] and root is not None:
		for node in queue:
			if node.right:
				level.append(node.right)
			if node.left:
				level.append(node.left)
		result.append(node.data)
		queue = level
		level = []
	return result


def LeftView(root):
	q = [(root, 0)]
	d = {}
	if not root:
		return []
	while q:
		(node, level) = q.pop(0)
		if level not in d:
			d[level] = node.data
		if node.left:
			q.append((node.left, level + 1))
		if node.right:
			q.append((node.right, level + 1))
	return [d[i] for i in d.keys()]


def leftViewUtil(result, node, level):
	global max_level
	if node == None:
		return
	if max_level < level:
		result.append(node.data)
		max_level = level
	leftViewUtil(result, node.left, level + 1)
	leftViewUtil(result, node.right, level + 1)

def LeftView(root):
	global max_level
	max_level = 0
	result = []
	leftViewUtil(result, root, 1)
	return result


def LeftView(root):
	if not root:
		return []
	res = []
	q = [root]
	while q:
		s = len(q)
		for i in range(s):
			front = q.pop(0)
			if i == 0:
				res.append(front.data)
			if front.left:
				q.append(front.left)
			if front.right:
				q.append(front.right)
	return res


def LeftView(root):

	def leftview(root, level, ans):
		if root is None:
			return
		if len(ans) < level:
			ans.append(root.data)
		leftview(root.left, level + 1, ans)
		leftview(root.right, level + 1, ans)
	ans = []
	leftview(root, 1, ans)
	return ans


def LeftView(root):
	height = 1
	ans = []
	solve(root, height, ans)
	return ans

def solve(root, height, ans):
	if root is None:
		return
	if height > len(ans):
		ans.append(root.data)
	solve(root.left, height + 1, ans)
	solve(root.right, height + 1, ans)
	height -= 1


def LeftView(root):
	myMap = {}

	def recursiveLeftView(node, level, hashMap):
		if node is None:
			return
		if level not in hashMap:
			hashMap[level] = node.data
		recursiveLeftView(node.left, level + 1, hashMap)
		recursiveLeftView(node.right, level + 1, hashMap)
	recursiveLeftView(root, 0, myMap)
	return myMap.values()


def LeftView(root):
	ans = []
	if root is None:
		return []
	queue = [root]
	while queue:
		size = len(queue)
		for i in range(size):
			node = queue.pop(0)
			if i == 0:
				ans.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
	return ans


def LeftView(root):
	sol = []

	def left(head, level):
		if head and len(sol) == level:
			sol.append(head.data)
		if head and head.left:
			left(head.left, level + 1)
		if head and head.right:
			left(head.right, level + 1)
	left(root, 0)
	return sol


def LeftView(root):
	if not root:
		return []
	queue = [[root]]
	ans = [root.data]
	while queue:
		level = queue.pop(0)
		temp = []
		for node in level:
			if node.left:
				temp.append(node.left)
			if node.right:
				temp.append(node.right)
		if temp:
			queue.append(temp)
			ans.append(temp[0].data)
	return ans


def solve(root, d, lev):
	if root == None:
		return
	if lev not in d:
		d[lev] = root.data
	solve(root.left, d, lev + 1)
	solve(root.right, d, lev + 1)

def LeftView(root):
	d = {}
	lev = 0
	ans = []
	solve(root, d, lev)
	for i in d:
		ans.append(d[i])
	return ans


from collections import deque

def LeftView(root):
	if root is None:
		return []
	temp = root
	nodes = []
	q = deque()
	q.append(root)
	q.append('-')
	while q:
		temp = q.popleft()
		if temp == '-':
			if len(q):
				q.append('-')
				nodes.append('-')
		else:
			nodes.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
	ans = [root.data]
	for i in range(len(nodes) - 1):
		if nodes[i] == '-':
			ans.append(nodes[i + 1])
	return ans


def LeftView(root):
	hash = []

	def leftview(root, level=0):
		if root is None:
			return []
		if level == len(hash):
			hash.append(root.data)
		leftview(root.left, level + 1)
		leftview(root.right, level + 1)
		return hash
	return leftview(root)


from collections import deque

def LeftView(root):
	if root == None:
		return []
	q = deque([[root, 0]])
	d = {}
	while q:
		(node, line) = q.popleft()
		if line not in d:
			d[line] = node.data
		if node.left:
			q.append([node.left, line + 1])
		if node.right:
			q.append([node.right, line + 1])
	ans = []
	for k in sorted(d):
		ans.append(d[k])
	return ans


class Node:

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

def LeftView(root):
	if root is None:
		return []
	left_view = []
	level = [root]
	while level:
		left_view.append(level[0].data)
		temp = []
		for node in level:
			if node.left:
				temp.append(node.left)
			if node.right:
				temp.append(node.right)
		level = temp
	return left_view


def LeftView(root):
	stack = []

	def lview(root, level):
		if root == None:
			return
		if level == len(stack):
			stack.append(root.data)
		lview(root.left, level + 1)
		lview(root.right, level + 1)
	lview(root, 0)
	return stack


def LeftView(root):
	(arr, i) = ([], 0)
	solve(root, arr, i)
	return arr

def solve(root, arr, i):
	if root == None:
		return
	if len(arr) > i:
		pass
	else:
		arr.append(root.data)
	solve(root.left, arr, i + 1)
	solve(root.right, arr, i + 1)


def LeftView(root):
	if root == None:
		return []
	q = deque()
	q.append(root)
	result = []
	while q:
		curr_size = len(q)
		for i in range(curr_size):
			curr_node = q.popleft()
			if i == 0:
				result.append(curr_node.data)
			if curr_node.left:
				q.append(curr_node.left)
			if curr_node.right:
				q.append(curr_node.right)
	return result


def Traverse(root, depth):
	depth += 1
	dMap_left = {}
	dMap_right = {}
	if root.left is not None:
		dMap_left = Traverse(root.left, depth)
	if root.right is not None:
		dMap_right = Traverse(root.right, depth)
	dMap_right.update(dMap_left)
	dMap_right[depth] = root.data
	return dMap_right

def LeftView(root):
	if root is None or root.data is None:
		return []
	else:
		return Traverse(root, 0).values()


from collections import defaultdict

def printLeftView(root, out, level):
	if root == None:
		return
	if level not in out:
		out[level] = root.data
	printLeftView(root.left, out, level + 1)
	printLeftView(root.right, out, level + 1)

def LeftView(root):
	out = defaultdict()
	printLeftView(root, out, 0)
	return out.values()


def LeftView(root):
	if not root:
		return []
	q = [root]
	a = []
	while q:
		x = len(q)
		i = 0
		temp = []
		while i < x:
			z = q.pop(0)
			temp.append(z.data)
			if z.left:
				q.append(z.left)
			if z.right:
				q.append(z.right)
			i += 1
		a.append(temp[0])
	return a


def LeftView(root):
	if not root:
		return []
	que = deque()
	que.append((0, root))
	dic = {}
	while len(que) != 0:
		(col, temp) = que.popleft()
		if col not in dic:
			dic[col] = temp.data
		if temp.left:
			que.append((col + 1, temp.left))
		if temp.right:
			que.append((col + 1, temp.right))
	result = []
	for v in sorted(dic.keys()):
		result.append(dic[v])
	return result


def LeftView(root):
	if not root:
		return []
	stack = [[root]]
	result = []
	result.append(root.data)
	while stack:
		nodes = stack.pop()
		node_stack = []
		for node in nodes:
			if node.left:
				node_stack.append(node.left)
			if node.right:
				node_stack.append(node.right)
		if not node_stack:
			break
		result.append(node_stack[0].data)
		stack.append(node_stack)
	return result


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


def LeftView(root):
	array = []
	stack = []
	level = 0
	max_level = 0
	head = root
	if head:
		array.append(head.data)
	while head or len(stack) > 0:
		if head:
			if level > max_level:
				array.append(head.data)
				max_level = level
			stack.append((head, level))
			head = head.left
			level += 1
		else:
			(node, level) = stack.pop()
			head = node.right
			level += 1
	return array


from collections import deque

def LeftView(root):
	if root is None:
		return []
	ans = []
	queue = deque()
	queue.append(root)
	while queue:
		q_size = len(queue)
		ans.append(queue[0].data)
		for i in range(q_size):
			node = queue.popleft()
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
	return ans


def LeftView(root):
	result = []
	leftView(root, result, 0)
	return result

def leftView(node, result, level):
	if not node:
		return
	if level == len(result):
		result.append(node.data)
	leftView(node.left, result, level + 1)
	leftView(node.right, result, level + 1)


def LeftView(root):
	result = []
	leftView(root, result, 0)
	return result

def leftView(curr, result, currDepth):
	if not curr:
		return
	if currDepth == len(result):
		result.append(curr.data)
	leftView(curr.left, result, currDepth + 1)
	leftView(curr.right, result, currDepth + 1)


def fun(root, level, ds):
	if root == None:
		return
	if len(ds) == level:
		ds.append(root.data)
	fun(root.left, level + 1, ds)
	fun(root.right, level + 1, ds)

def LeftView(root):
	ds = []
	fun(root, 0, ds)
	return ds


def LeftView(root):
	if root is None:
		return []
	stack = [(root, 0)]
	result = []
	level_seen = set()
	while stack:
		(node, level) = stack.pop()
		if node is None:
			continue
		if level not in level_seen:
			result.append(node.data)
			level_seen.add(level)
		stack.append((node.right, level + 1))
		stack.append((node.left, level + 1))
	return result


def LeftView(root):
	maxlevel = [0]
	ans = []
	lef(root, 1, maxlevel, ans)
	return ans

def lef(root, level, maxlevel, ans):
	if root is None:
		return
	if maxlevel[0] < level:
		ans.append(root.data)
		maxlevel[0] = level
	lef(root.left, level + 1, maxlevel, ans)
	lef(root.right, level + 1, maxlevel, ans)


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


def getleftView(root, level, maxLevel):
	left_view = []
	if not root:
		return
	if maxLevel[0] < level:
		left_view.append(root.data)
		maxLevel[0] = level
	getleftView(root.left, level + 1, maxLevel)
	getleftView(root.right, level + 1, maxLevel)
	return left_view

def LeftView(root):
	s = []

	def left(root, level):
		if root is None:
			return
		if level == len(s):
			s.append(root.data)
		left(root.left, level + 1)
		left(root.right, level + 1)
	left(root, 0)
	return s


from collections import deque

def LeftView(root):
	if not root:
		return []
	queue = deque()
	ans = []
	queue.append(root)
	while len(queue):
		size = len(queue)
		flag = True
		while size:
			curr_node = queue.popleft()
			if flag:
				ans.append(curr_node.data)
				flag = False
			if curr_node.left:
				queue.append(curr_node.left)
			if curr_node.right:
				queue.append(curr_node.right)
			size = size - 1
	return ans


def LeftView(root):
	ans = []
	if root is None:
		return ans
	q = deque([])
	q.append(root)
	while len(q) != 0:
		level = len(q)
		for i in range(level):
			current = q.popleft()
			if i == 0:
				ans.append(current.data)
			if current.left is not None:
				q.append(current.left)
			if current.right is not None:
				q.append(current.right)
	return ans


def LeftViewUtil(root, ans, level, maxlevel):
	if root:
		if level > maxlevel[0]:
			maxlevel[0] = level
			ans.append(root.data)
		LeftViewUtil(root.left, ans, level + 1, maxlevel)
		LeftViewUtil(root.right, ans, level + 1, maxlevel)

def LeftView(root):
	ans = []
	LeftViewUtil(root, ans, 0, [-1])
	return ans


def LeftView(root):
	if not root:
		return []
	left_view = []
	queue = deque([root])
	while queue:
		level_size = len(queue)
		left_view.append(queue[0].data)
		for _ in range(level_size):
			node = queue.popleft()
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
	return left_view


def LeftView(root):
	if root is None:
		return []
	res = []
	q = deque()
	q.append(root)
	while q:
		count = len(q)
		for i in range(count):
			currN = q.popleft()
			if i == 0:
				res.append(currN.data)
			if currN.left:
				q.append(currN.left)
			if currN.right:
				q.append(currN.right)
	return res


def LeftView(root):
	if root is None:
		return []
	l = []
	q = deque()
	q.append(root)
	while q:
		i = 0
		s = len(q)
		while i < s:
			currN = q.popleft()
			i += 1
			if i == 1:
				l.append(currN.data)
			if currN.left:
				q.append(currN.left)
			if currN.right:
				q.append(currN.right)
	return l


def preordertraversal(root, level, maxlevel, leftview):
	if root is None:
		return maxlevel
	if maxlevel < level:
		leftview.append(root.data)
		maxlevel = level
	maxlevel = preordertraversal(root.left, level + 1, maxlevel, leftview)
	maxlevel = preordertraversal(root.right, level + 1, maxlevel, leftview)
	return maxlevel

def LeftView(root):
	leftview = []
	maxlevel = -1
	maxlevel = preordertraversal(root, 0, maxlevel, leftview)
	return leftview


def LeftView(root):
	values = []
	global max_level
	max_level = 0

	def LeftViewRec(node, current_level, values):
		global max_level
		if node is None:
			return
		if max_level < current_level:
			max_level = current_level
			values.append(node.data)
		LeftViewRec(node.left, current_level + 1, values)
		LeftViewRec(node.right, current_level + 1, values)
	LeftViewRec(root, 1, values)
	return values


from collections import defaultdict, deque

def LeftView(root):
	if root is None:
		return []
	dist_map = {}
	q = deque()
	q.append((root, 0))
	data = []
	while q:
		(node, d) = q.popleft()
		data.append(d)
		if d >= 0 and dist_map.get(d) is None:
			dist_map[d] = node.data
		if node.left:
			q.append((node.left, d + 1))
		if node.right:
			q.append((node.right, d + 1))
	distances = list(dist_map.keys())
	distances.sort()
	ans = [dist_map[d] for d in distances]
	return ans


from collections import defaultdict, deque

def LeftView(root):
	if root is None:
		return []
	try:
		dist_map = {}
		q = deque()
		q.append((root, 0))
		data = []
		while q:
			(node, d) = q.popleft()
			data.append(d)
			if d >= 0 and dist_map.get(d) is None:
				dist_map[d] = node.data
			if node.left:
				q.append((node.left, d + 1))
			if node.right:
				q.append((node.right, d + 1))
		distances = list(dist_map.keys())
		distances.sort()
		ans = [dist_map[d] for d in distances]
		return ans
	except Exception as e:
		print(data)
		print(dist_map)
		print(e)
		return []


def ape(root, res, level):
	if root is None:
		return
	if len(res) < level:
		res.append(root.data)
	ape(root.left, res, level + 1)
	ape(root.right, res, level + 1)

def LeftView(root):
	res = []
	ape(root, res, 1)
	return res


def LeftView(root):
	if root is None:
		return []
	ans = []
	q = []
	q.append(root)
	while q:
		n = len(q)
		sub = []
		count = 0
		for i in range(n):
			rn = q.pop(0)
			if count < 1:
				sub.append(rn.data)
				count += 1
			if rn.left is not None:
				q.append(rn.left)
			if rn.right is not None:
				q.append(rn.right)
		ans.append(sub[0])
	return ans


def LeftView(root):
	d = {}

	def h(root, lvl=0):
		if root == None:
			return
		if lvl not in d:
			d[lvl] = root.data
		h(root.left, lvl + 1)
		h(root.right, lvl + 1)
	ans = []
	h(root)
	for i in range(len(d)):
		ans.append(d[i])
	return ans


def leftViewUtil(root, level, max_level, res):
	if root is None:
		return
	if max_level[0] < level:
		res.append(root.data)
		max_level[0] = level
	leftViewUtil(root.left, level + 1, max_level, res)
	leftViewUtil(root.right, level + 1, max_level, res)

def LeftView(root):
	res = []
	max_level = [0]
	leftViewUtil(root, 1, max_level, res)
	return res


def LeftView(root):
	if not root:
		return []
	queue = [root]
	answer = []
	while queue:
		size = len(queue)
		for i in range(size):
			node = queue.pop(0)
			if i == 0:
				answer.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
	return answer


from collections import deque

def LeftView(root):

	def preOrder(node, level):
		if not node:
			return
		if level == len(result):
			result.append(node.data)
		preOrder(node.left, level + 1)
		preOrder(node.right, level + 1)
	result = []
	preOrder(root, 0)
	return result


def LeftView(root):
	arr = []

	def leftview(root, arr, level):
		if root == None:
			return
		if level == len(arr):
			arr.append(root.data)
		leftview(root.left, arr, level + 1)
		leftview(root.right, arr, level + 1)
	leftview(root, arr, 0)
	return arr


def LeftView(root):
	if root is None:
		return []
	queue = [[root, 0]]
	res = {}
	while queue:
		fwd = []
		while queue:
			val = queue.pop(0)
			if val[0].left:
				fwd.append([val[0].left, val[1] + 1])
			if val[0].right:
				fwd.append([val[0].right, val[1] + 1])
			if val[1] not in res:
				res[val[1]] = val[0].data
		queue = fwd
	ans = []
	for i in sorted(res.keys()):
		ans.append(res[i])
	return ans


from collections import deque

def LeftView(root):
	if not root:
		return []
	result = []
	queue = deque([root])
	while queue:
		n = len(queue)
		for i in range(n):
			node = queue.popleft()
			if i == 0:
				result.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
	return result


def util(root, l, ml, res):
	if root is None:
		return
	if l > ml[0]:
		res.append(root.data)
		ml[0] = l
	util(root.left, l + 1, ml, res)
	util(root.right, l + 1, ml, res)

def LeftView(root):
	ml = [0]
	res = []
	util(root, 1, ml, res)
	return res


def LeftView(root):
	val = []
	val.append(root)
	ret = []
	while val:
		n = len(val)
		for i in range(n):
			curr = val.pop(0)
			if curr == None:
				break
			if i == 0:
				ret.append(curr.data)
			if curr.left:
				val.append(curr.left)
			if curr.right:
				val.append(curr.right)
	return ret


def LeftView(root):
	if root == None:
		return []
	q = []
	q.append(root)
	ans = []
	flg = 1
	while len(q) != 0:
		size = len(q)
		tmp = []
		while size != 0:
			curr = q.pop(0)
			tmp.append(curr.data)
			if curr.left != None:
				q.append(curr.left)
			if curr.right != None:
				q.append(curr.right)
			size -= 1
		ans.append(tmp[0])
	return ans


def LeftView(root):
	p = root
	if not p:
		return []
	out = []
	while 1:
		out.append(p.data)
		if p.left:
			p = p.left
		elif p.right:
			p = p.right
		else:
			break
	p = root.right
	if not p:
		return out
	out1 = []
	while 1:
		out1.append(p.data)
		if p.left:
			p = p.left
		elif p.right:
			p = p.right
		else:
			break
	m = out1[len(out) - 1:]
	return out + m


def get_left_view(root, a, level):
	if root == None:
		return
	global max_level
	if max_level < level:
		a.append(root.data)
		max_level = level
	get_left_view(root.left, a, level + 1)
	get_left_view(root.right, a, level + 1)

def LeftView(root):
	global max_level
	max_level = 0
	a = list()
	get_left_view(root, a, 1)
	return a


def solve(root, level, maxlevel, ll):
	if root is None:
		return
	if maxlevel[0] < level:
		ll.append(root.data)
		maxlevel[0] = level
	solve(root.left, level + 1, maxlevel, ll)
	solve(root.right, level + 1, maxlevel, ll)

def LeftView(root):
	l = [0]
	ll = []
	solve(root, 1, l, ll)
	return ll


def LeftView(root):
	if root == None:
		return []
	queue = []
	ans = []
	queue.append(root)
	while queue:
		n = len(queue)
		a = n
		while n > 0:
			temp = queue.pop(0)
			if n == a:
				ans.append(temp.data)
			if temp.left != None:
				queue.append(temp.left)
			if temp.right != None:
				queue.append(temp.right)
			n -= 1
	return ans


def LeftView(root):
	queue = []
	if root:
		queue.append(root)
	level = 0
	ans = []
	while queue:
		level += 1
		for i in range(len(queue)):
			m = queue.pop(0)
			if level == 1:
				ans.append(m.data)
			if m.left:
				queue.append(m.left)
			if m.right:
				queue.append(m.right)
			level = 0
	return ans


def LeftView(root):
	if root is None:
		return []
	queue = []
	ans = []
	queue.append(root)
	while len(queue) > 0:
		level = []
		for i in range(len(queue)):
			root = queue[0]
			queue.pop(0)
			if root.left:
				queue.append(root.left)
			if root.right:
				queue.append(root.right)
			level.append(root.data)
		ans.append(level)
	res = []
	for i in range(len(ans)):
		res.append(ans[i][0])
	return res


def LeftView(root):
	runner = root
	stack = []
	prelvl = -1
	stack.append((root, 0))
	ans = []
	while stack:
		(cur, lvl) = stack.pop()
		if not cur:
			continue
		if lvl > prelvl:
			ans.append(cur.data)
			prelvl = lvl
		stack.append((cur.right, lvl + 1))
		stack.append((cur.left, lvl + 1))
	return ans


def LeftView(root):
	if not root:
		return []
	result = []
	max_depth = -1

	def traverse(node, depth):
		nonlocal max_depth
		if not node:
			return
		if depth > max_depth:
			result.append(node.data)
			max_depth = depth
		traverse(node.left, depth + 1)
		traverse(node.right, depth + 1)
	traverse(root, 0)
	return result


def LeftView(root):
	maxLevel = 0
	res = []

	def leftViewUtil(node, level):
		nonlocal maxLevel
		if node:
			if level > maxLevel:
				res.append(node.data)
				maxLevel = level
			leftViewUtil(node.left, level + 1)
			leftViewUtil(node.right, level + 1)
	leftViewUtil(root, 1)
	return res