Given a Binary Tree of size N, Print the corner nodes ie- the node at the leftmost and rightmost of each level.
Example 1:
Input :
         1
       /  \
     2      3
    / \    / \
   4   5  6   7    
Output: 1 2 3 4 7
Explanation:
Corners at level 0: 1
Corners at level 1: 2 3
Corners at level 2: 4 7
Example 2:
Input:
        10
      /    \
     20     30
    / \  
   40  60
Output: 10 20 30 40 60
Your Task:  
You dont need to read input. Complete the function printCorner() which takes root node as input parameter and prints the corner nodes separated by spaces. The left corner should be printed before the right for each level starting from level 0.
Note: Don't print a new line after printing all the corner nodes.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(number of nodes in a level)
Constraints:
1 ≤ N ≤ 10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



#User function Template for python3



'''

class Node:

    def _init_(self,val):

        self.data=val

        self.left=None

        self.right=None

'''



def printCorner(root):

    

    # print corner data, no need to print new line

    # code here









Solutions:
def printCorner(root):
	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 len(temp) > 1:
			queue.append(temp)
			ans.append(temp[0].data)
			ans.append(temp[-1].data)
		elif len(temp) == 1:
			queue.append(temp)
			ans.append(temp[0].data)
	for i in ans:
		print(i, end=' ')


def printCorner(root):
	q = [root]
	while len(q) > 0:
		l = len(q)
		for i in range(l):
			temp = q[0]
			q.pop(0)
			if i == 0 or i == l - 1:
				print(temp.data, end=' ')
			if temp.left != None:
				q.append(temp.left)
			if temp.right != None:
				q.append(temp.right)
	return


def printCorner(root):
	q = [root]
	ans = []
	while q:
		lis = []
		for i in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			lis.append(node.data)
		if len(lis) > 1:
			ans.append(lis[0])
			ans.append(lis[-1])
		else:
			ans.append(lis[0])
	for i in ans:
		print(i, end=' ')


def printCorner(root):
	out = []
	queue = [root, '\n']
	temp = []
	while len(queue) > 1:
		if not queue[0]:
			queue.pop(0)
			continue
		if queue[0] == '\n':
			out.append(temp)
			temp = []
			queue.pop(0)
			queue.append('\n')
			continue
		queue.extend([queue[0].left, queue[0].right])
		temp.extend([queue[0].data])
		queue.pop(0)
	res = []
	for i in range(len(out)):
		if len(out[i]) == 1:
			res += [out[i][0]]
		else:
			res.extend([out[i][0], out[i][-1]])
	for i in res:
		print(i, end=' ')


def printCorner(root):
	ans = []
	q = deque()
	q.append(root)
	while q:
		n = len(q)
		for i in range(n):
			p = q.popleft()
			if i == 0 or i == n - 1:
				ans.append(p.data)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
	for i in ans:
		print(i, end=' ')


def printCorner(root):
	q = [root]
	while len(q) > 0:
		l = len(q)
		inlen = l
		while l > 0:
			temp = q[0]
			if l == inlen:
				print(temp.data, end=' ')
			elif l == 1 and inlen > 1:
				print(temp.data, end=' ')
			q.pop(0)
			if temp.left != None:
				q.append(temp.left)
			if temp.right != None:
				q.append(temp.right)
			l -= 1
	return


from collections import deque

def printCorner(root):
	if not root:
		return None
	q = deque()
	q.append(root)
	while len(q):
		n = len(q)
		for i in range(n):
			curr = q.popleft()
			if i == 0 or i == n - 1:
				print(curr.data, end=' ')
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
	return None


def printCorner(root):
	q = []
	q.append(root)
	print(q[0].data, end=' ')
	while q:
		n = len(q)
		while n > 0:
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			n -= 1
		if q:
			if len(q) > 1:
				print(q[0].data, end=' ')
				print(q[-1].data, end=' ')
			else:
				print(q[0].data, end=' ')


import collections

def printCorner(root):
	q = collections.deque()
	q.append(root)
	first = 1
	while q:
		qLen = len(q)
		f = 0
		for i in range(qLen):
			cur = q.popleft()
			if not f:
				print(cur.data, end=' ')
				check = cur
				f = 1
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
		if cur != check:
			print(cur.data, end=' ')


import collections

def printCorner(root):
	q = collections.deque()
	q.append(root)
	while len(q) != 0:
		n = len(q)
		for i in range(n):
			pop_node = q.popleft()
			if i == 0 or i == n - 1:
				print(pop_node.data, end=' ')
			if pop_node.left != None:
				q.append(pop_node.left)
			if pop_node.right != None:
				q.append(pop_node.right)


from collections import deque

def printCorner(root):
	dq = deque()
	dq.append(root)
	while len(dq) > 0:
		currsize = len(dq)
		for i in range(currsize):
			temp = dq.popleft()
			if i == 0 or i == currsize - 1:
				print(temp.data, end=' ')
			if temp.left != None:
				dq.append(temp.left)
			if temp.right != None:
				dq.append(temp.right)


def printCorner(root):

	def helper(root):
		ans = []
		t = []
		q = []
		if not root:
			return ans
		q.append(root)
		while q:
			for i in range(len(q)):
				a = q.pop(0)
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
				t.append(a.data)
			if len(t) > 1:
				ans.append(t[0])
				ans.append(t[-1])
			elif len(t) == 1:
				ans.append(t[0])
			t = []
		return ans
	a = helper(root)
	for i in a:
		print(i, end=' ')


from queue import Queue

def printCorner(root):
	ans = []
	if root == None:
		return ans
	q = Queue()
	q.put(root)
	while not q.empty():
		size = q.qsize()
		l = []
		for i in range(size):
			node = q.get()
			if node and node.left:
				q.put(node.left)
			if node and node.right:
				q.put(node.right)
			if node:
				l.append(node.data)
		if len(l) == 1:
			ans += l
		else:
			ans += [l[0], l[-1]]
	for x in ans:
		print(x, end=' ')


def printCorner(root):
	q = []
	q.append(root)
	l = []
	while len(q):
		count = len(q)
		sl = []
		while count > 0:
			p = q.pop(0)
			sl.append(p.data)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
			count -= 1
		l.append(sl)
	for i in l:
		if len(i) == 1:
			print(i[0], end=' ')
		else:
			print(i[0], end=' ')
			print(i[-1], end=' ')


def printCorner(root):
	a1 = {}
	queue = [root]
	queue1 = [0]
	while len(queue) > 0:
		x = queue.pop(0)
		y = queue1.pop(0)
		if y not in a1:
			a1[y] = []
		a1[y].append(x.data)
		if x.left:
			queue.append(x.left)
			queue1.append(y + 1)
		if x.right:
			queue.append(x.right)
			queue1.append(y + 1)
	d = []
	for i in range(max(a1) + 1):
		d.append(a1[i][0])
		if len(a1[i]) > 1:
			d.append(a1[i][-1])
	for i in d:
		print(i, end=' ')


def printCorner(root):
	q = []
	q.append(root)
	lis = []
	ans = []
	while q:
		l = len(q)
		lis = []
		for i in range(l):
			temp = q.pop(0)
			lis.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		if len(lis) == 1:
			ans.extend(lis)
		elif len(lis) > 1:
			ans.append(lis[0])
			ans.append(lis[-1])
	for i in ans:
		print(i, end=' ')


import sys
sys.setrecursionlimit(10 ** 6)

def printCorner(root):
	dic = {}
	maxL = 0

	def recursive(root, lvl=1):
		nonlocal dic, maxL
		if root is None:
			return
		maxL = max(maxL, lvl)
		if lvl not in dic:
			dic[lvl] = [root.data]
		else:
			if len(dic[lvl]) == 2:
				dic[lvl].pop()
			dic[lvl].append(root.data)
		recursive(root.left, lvl + 1)
		recursive(root.right, lvl + 1)
	recursive(root)
	ans = []
	lvl = 1
	while lvl in dic:
		print(*dic[lvl], end=' ')
		lvl += 1


def printCorner(root):
	li = []
	res = []
	que = [root]
	li.append(root.data)
	while que:
		ans = []
		for i in range(len(que)):
			node = que.pop(0)
			if node.left:
				ans.append(node.left.data)
				que.append(node.left)
			if node.right:
				ans.append(node.right.data)
				que.append(node.right)
		if ans and len(ans) >= 2:
			li.append(ans[0])
			li.append(ans[-1])
		elif ans and len(ans) == 1:
			li.append(ans[0])
	for i in li:
		print(i, end=' ')


def printCorner(root):
	if root is None:
		return []
	ans = []
	q = []
	q.append(root)
	while len(q) > 0:
		t = []
		if len(q) == 1:
			ans.append(q[0])
		else:
			ans.append(q[0])
			ans.append(q[-1])
		while len(q) != 0:
			x = q.pop(0)
			if x.left is not None:
				t.append(x.left)
			if x.right is not None:
				t.append(x.right)
		q = t
	for i in ans:
		print(i.data, end=' ')


def printCorner(root):
	store = []
	tree = [(root, 0)]
	while tree:
		(head, level) = tree.pop()
		if not head:
			continue
		if len(store) == level:
			store.append([])
		store[level].append(head.data)
		tree.append((head.right, level + 1))
		tree.append((head.left, level + 1))
	for item in store:
		print(item[0], end=' ')
		if len(item) > 1:
			print(item[-1], end=' ')
	return


def printCorner(root):
	queue = [root]
	while queue != []:
		t = []
		for i in range(len(queue)):
			curr = queue[0]
			if curr.left:
				queue.append(curr.left)
			if curr.right:
				queue.append(curr.right)
			t.append(curr.data)
			queue.pop(0)
		if len(t) == 1:
			print(t[0], end=' ')
		else:
			print(t[0], end=' ')
			print(t[-1], end=' ')


def printCorner(root):
	p = [0]
	q = [root]
	g = {}
	while len(q) > 0:
		a = p.pop(0)
		b = q.pop(0)
		if a not in g:
			g[a] = [b.data]
		else:
			g[a].append(b.data)
		if b.left != None:
			q.append(b.left)
			p.append(a + 1)
		if b.right != None:
			q.append(b.right)
			p.append(a + 1)
	for x in g:
		c = len(g[x])
		d = g[x]
		if c == 1:
			print(d[0], end=' ')
		else:
			print(d[0], end=' ')
			print(d[c - 1], end=' ')


def printCorner(root):
	stack = [root]
	print(root.data, end=' ')
	while stack:
		n = len(stack)
		while n != 0:
			top = stack.pop(0)
			if top.left:
				stack.append(top.left)
			if top.right:
				stack.append(top.right)
			n -= 1
		if len(stack) > 1:
			(a, b) = (stack[0].data, stack[-1].data)
			print(a, b, end=' ')
		elif stack:
			print(stack[-1].data, end=' ')


from collections import deque

def printCorner(root):
	if not root:
		return []
	(queue, result) = (deque([root]), [])
	while queue:
		length = len(queue)
		for i in range(len(queue)):
			node = queue.popleft()
			if i == 0 or i == length - 1:
				result.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
	for element in result:
		print(element, end=' ')


def printCorner(root):
	k = 0
	d = dict()
	res = []
	q = []
	q.append((root, 0))
	while len(q) > 0:
		(c, k) = q.pop(-1)
		if k not in d:
			d[k] = []
		d[k].append(c.data)
		if c.left:
			q.append((c.left, k + 1))
		if c.right:
			q.append((c.right, k + 1))
	for i in list(d.keys()):
		if len(d[i]) > 1:
			print(d[i][-1], end=' ')
			print(d[i][0], end=' ')
		else:
			print(d[i][0], end=' ')


def printCorner(root):
	q = list()
	level = dict()
	q.append([root, 0])
	while q:
		(cur, dist) = q.pop(0)
		level[dist] = level.get(dist, []) + [cur.data]
		if cur.left:
			q.append([cur.left, dist + 1])
		if cur.right:
			q.append([cur.right, dist + 1])
	for i in sorted(level):
		if level.get(i):
			if len(level[i]) == 1:
				print(level[i][0], end=' ')
			else:
				print(level[i][0], level[i][-1], end=' ')
		else:
			break


def printCorner(root):
	q = [root]
	while q:
		n = len(q)
		curr = []
		for i in range(n):
			node = q[0]
			del q[0]
			if node:
				curr.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if len(curr) >= 2:
			print(curr[0], end=' ')
			print(curr[-1], end=' ')
		elif curr and curr[0]:
			print(curr[0], end=' ')


def printCorner(root):
	if root is None:
		return
	if not root.left and (not root.right):
		print(root.data)
		return
	(q, res) = ([root], [root.data])
	while q:
		nq = []
		for i in q:
			if i.left:
				nq.append(i.left)
			if i.right:
				nq.append(i.right)
		if len(nq) == 0:
			break
		elif len(nq) == 1:
			res.append(nq[0].data)
		elif len(nq) > 1:
			res.extend([nq[0].data, nq[-1].data])
		q = nq
	for i in res:
		print(i, end=' ')


def printCorner(root):
	mainL = []
	q = []
	q.append(root)
	if root == None:
		return mainL
	p = 0
	while len(q) > 0:
		subL = []
		for i in range(len(q)):
			temp = q[0]
			q.remove(q[0])
			if temp.left is not None:
				q.append(temp.left)
			if temp.right is not None:
				q.append(temp.right)
			subL.append(temp.data)
			p += 1
		if len(subL) == 1:
			print(subL[0], end=' ')
		else:
			print(subL[0], subL[-1], end=' ')


def printCorner(root):
	l = []
	q = [root]
	while q:
		t = len(q)
		tmp = []
		while t > 0:
			s = q.pop(0)
			if s.left:
				q.append(s.left)
			if s.right:
				q.append(s.right)
			tmp.append(s.data)
			t -= 1
		if len(tmp) == 1:
			l.append(tmp[0])
		else:
			l.append(tmp[0])
			l.append(tmp[-1])
	for i in l:
		print(i, end=' ')


from collections import deque

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

def printCorner(root):
	q = queue()
	q.enqueue(root)
	result = []
	while q.isempty() != True:
		count = q.size
		counthigh = q.size
		while count != 0:
			temp = q.dequeue()
			if temp.left:
				q.enqueue(temp.left)
			if temp.right:
				q.enqueue(temp.right)
			if count == counthigh and count != 1:
				result.append(temp.data)
			count -= 1
			if count == 0:
				result.append(temp.data)
	for i in result:
		print(i, end=' ')


def printCorner(root):
	if root == None:
		return
	d = deque()
	final = []
	d.append(root)
	while len(d) > 0:
		r = []
		for i in d:
			r.append(i.data)
		l = len(d)
		for i in range(l):
			node = d.popleft()
			if node.left:
				d.append(node.left)
			if node.right:
				d.append(node.right)
		if len(r) >= 2:
			print(r[0], r[-1], end=' ')
		else:
			print(r[0], end=' ')
	return


def printCorner(root):
	x = []
	q = deque()
	t = []
	if not root:
		return x
	q.append(root)
	while q:
		for i in range(len(q)):
			a = q.popleft()
			if a.left:
				q.append(a.left)
			if a.right:
				q.append(a.right)
			t.append(a.data)
		if len(t) == 1:
			x.append(t[0])
		else:
			x.append(t[0])
			x.append(t[-1])
		t = []
	for i in x:
		print(i, end=' ')


def printCorner(root):
	if not root:
		return
	q = [root]
	last_level = []
	while q:
		count = len(q)
		for i in range(count):
			node = q.pop(0)
			if i == 0 or i == count - 1:
				print(node.data, end=' ')
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)


def printCorner(root):
	ans = []
	q = [root]
	while q:
		n = len(q)
		for i in range(n):
			node = q.pop(0)
			if i == 0 or i == n - 1:
				ans.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	for val in ans:
		print(val, end=' ')


def printCorner(root):
	ans = []
	queue = [root]
	level = []
	while queue != [] and root is not None:
		l = []
		for node in queue:
			l.append(node.data)
			if node.left:
				level.append(node.left)
			if node.right:
				level.append(node.right)
		if len(l) == 1:
			print(l[0], end=' ')
		else:
			print(l[0], end=' ')
			print(l[-1], end=' ')
		queue = level
		level = []


from collections import deque

def printCorner(root):
	res = []
	if root is None:
		return res
	q = deque()
	q.append(root)
	level = []
	while q:
		n = len(q)
		for i in range(n):
			node = q.popleft()
			if i == 0 or i == n - 1:
				level.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	for i in level:
		print(i, end=' ')


def printCorner(root):
	(q1, q2) = ([], [root])
	while q2:
		(q1, q2) = (q2, q1)
		q2.clear()
		for nd in q1:
			if nd.left:
				q2.append(nd.left)
			if nd.right:
				q2.append(nd.right)
		if len(q1) > 1:
			print(q1[0].data, q1[-1].data, end=' ')
		else:
			print(q1[0].data, end=' ')


from collections import deque

def printCorner(root):
	q = deque()
	q.append(root)
	while q:
		n = len(q)
		print(q[0].data, end=' ')
		if n > 1:
			print(q[-1].data, end=' ')
		for i in range(n):
			nod = q.popleft()
			if nod.left:
				q.append(nod.left)
			if nod.right:
				q.append(nod.right)


class Node:

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

def printCorner(root):
	lst = []
	if root is None:
		return None
	else:
		import collections
		q = collections.deque()
		q.append(root)
		while q:
			level = []
			for i in range(len(q)):
				node = q.popleft()
				if node:
					level.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if len(level) == 1:
				lst.append(level[0])
			else:
				lst.append(level[0])
				lst.append(level[len(level) - 1])
		for i in lst:
			print(i, end=' ')


def printCorner(root):
	result = []
	queue = [root]
	while queue:
		(length, index) = (len(queue), 0)
		while index < length:
			node = queue.pop(0)
			if index == 0 or index == length - 1:
				print(node.data, end=' ')
				result.append(node.data)
			if node.left != None:
				queue.append(node.left)
			if node.right != None:
				queue.append(node.right)
			index += 1
	return result


def printCorner(root):
	print(root.data, end=' ')
	q = []
	q.append(root)
	while len(q):
		n = len(q)
		l = []
		for i in range(n):
			curr = q.pop(0)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
		if len(q) == 0:
			break
		print(q[0].data, end=' ')
		if len(q) == 1:
			continue
		print(q[-1].data, end=' ')


def printCorner(root):
	if root == None:
		return
	q = deque()
	q.append(root)
	while q:
		n = len(q)
		for i in range(n):
			temp = q[0]
			q.popleft()
			if i == 0 or i == n - 1:
				print(temp.data, end=' ')
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)


def printCorner(root):
	q = [root]
	ans = []
	while q:
		a = len(q)
		l = []
		for i in range(a):
			x = q.pop(0)
			if x.left:
				q.append(x.left)
			if x.right:
				q.append(x.right)
			l.append(x.data)
		ans.append(l)
	fans = []
	for i in ans:
		if len(i) == 1:
			fans.append(i[0])
		else:
			fans.append(i[0])
			fans.append(i[-1])
	for i in fans:
		print(i, end=' ')


def printCorner(root):
	s = {}
	q = [[root, 0]]
	c = 0
	m = -1
	while c != len(q):
		t = q[c][0]
		g = q[c][1]
		if g > m:
			m = g
		if g in s:
			s[g][1] = t.data
		else:
			s[g] = [t.data, -1]
		if t.left:
			q.append([t.left, g + 1])
		if t.right:
			q.append([t.right, g + 1])
		c += 1
	for i in range(m + 1):
		for j in s[i]:
			if j != -1:
				print(j, end=' ')


from collections import *

def printCorner(root):
	queue = deque([root])
	ans = []
	s = set()
	while queue:
		l = True
		for _ in range(len(queue)):
			t = queue.popleft()
			if l:
				print(t.data, end=' ')
				s.add(t)
				l = False
			if t.left:
				queue.append(t.left)
			if t.right:
				queue.append(t.right)
		if t not in s:
			print(t.data, end=' ')


def printCorner(root):
	if root is None:
		return []
	if root.left and root.right:
		que = [root.left, root.right]
	elif root.left:
		que = [root.left]
	else:
		que = [root.right]
	ans = [root.data]
	while que != []:
		temp = []
		for i in range(len(que)):
			if i == 0 or i == len(que) - 1:
				if que[i] is not None:
					ans.append(que[i].data)
			if que[i].left:
				temp.append(que[i].left)
			if que[i].right:
				temp.append(que[i].right)
		que = temp
	for i in ans:
		print(i, end=' ')


def printCorner(root):
	if not root.left and (not root.right):
		return [root.data]
	queue = []
	queue.append(root)
	a = []
	while queue:
		count = len(queue)
		ans = []
		while count:
			temp = queue.pop(0)
			ans.append(temp.data)
			if temp.left:
				queue.append(temp.left)
			if temp.right:
				queue.append(temp.right)
			count -= 1
		if len(ans) == 1:
			a.append(ans[0])
		else:
			a.append(ans[0])
			a.append(ans[-1])
	for i in range(len(a)):
		print(a[i], end=' ')


def printCorner(root):
	ans = []
	level = []
	queue = [root]
	while queue:
		l = []
		for root in queue:
			l.append(root.data)
			if root.left:
				level.append(root.left)
			if root.right:
				level.append(root.right)
		if len(l) == 1:
			print(l[0], end=' ')
		else:
			print(l[0], end=' ')
			print(l[-1], end=' ')
		queue = level
		level = []


from collections import deque

def printCorner(root):
	q = deque()
	q.append(root)
	answer = []
	while q:
		l = len(q)
		for i in range(l):
			node = q.popleft()
			if i == 0 or i == l - 1:
				answer.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	for i in answer:
		print(i, end=' ')


def levelOrderTraversal(root, level, hd, level_order_traversal):
	if not root:
		return
	if level not in level_order_traversal:
		level_order_traversal[level] = [(root.data, hd)]
	else:
		level_order_traversal[level].append((root.data, hd))
	levelOrderTraversal(root.left, level + 1, hd - 1, level_order_traversal)
	levelOrderTraversal(root.right, level + 1, hd + 1, level_order_traversal)

def printCorner(root):
	level_order_traversal = []
	level_order_traversal.append(root)
	level_view_left_right = []
	while len(level_order_traversal) > 0:
		length = len(level_order_traversal)
		for i in range(length):
			first_elem = level_order_traversal[0]
			level_order_traversal.remove(level_order_traversal[0])
			if i == 0:
				level_view_left_right.append(first_elem.data)
			if length > 1 and i == length - 1:
				level_view_left_right.append(first_elem.data)
			if first_elem.left:
				level_order_traversal.append(first_elem.left)
			if first_elem.right:
				level_order_traversal.append(first_elem.right)
	for elem in level_view_left_right:
		print(elem, end=' ')


def printCorner(root):
	a = []
	if root == None:
		return a
	q1 = []
	q1.append(root)
	f = 1
	while len(q1) != 0:
		temp = []
		s = len(q1)
		while s > 0:
			t = q1[0]
			temp.append(t.data)
			q1.pop(0)
			if t.left:
				q1.append(t.left)
			if t.right:
				q1.append(t.right)
			s = s - 1
		a.append(temp)
	m = []
	for i in range(len(a)):
		if len(a[i]) == 1:
			m.append(a[i][0])
		else:
			m.append(a[i][0])
			m.append(a[i][-1])
	for i in m:
		print(i, end=' ')


def printCorner(root):
	queue = [root]
	while queue:
		n = len(queue)
		for i in range(n):
			cur = queue.pop(0)
			if i == 0 or i == n - 1:
				print(cur.data, end=' ')
			if cur.left:
				queue.append(cur.left)
			if cur.right:
				queue.append(cur.right)


def printCorner(root):
	ans = []
	if root is None:
		return ans
	q = []
	q.append(root)
	while q:
		length = len(q)
		for i in range(length):
			cur_node = q.pop(0)
			if i == 0 or i == length - 1:
				ans.append(cur_node.data)
			if cur_node.left:
				q.append(cur_node.left)
			if cur_node.right:
				q.append(cur_node.right)
	for i in ans:
		print(i, end=' ')


from collections import deque

def printCorner(root):
	if root is None:
		return False
	q = deque()
	q.append(root)
	while q:
		n = len(q)
		te = n
		while n > 0:
			t = q.popleft()
			if n == te or n == 1:
				print(t.data, end=' ')
			if t.left:
				q.append(t.left)
			if t.right:
				q.append(t.right)
			n -= 1


def printCorner(root):
	que = deque([root])
	while que:
		n = len(que)
		for i in range(n):
			curr = que.popleft()
			if i == 0 or i == n - 1:
				print(curr.data, end=' ')
			if curr.left:
				que.append(curr.left)
			if curr.right:
				que.append(curr.right)


def printCorner(root):
	queue = [root]
	while queue:
		temp = []
		for e in queue:
			if e.left:
				temp.append(e.left)
			if e.right:
				temp.append(e.right)
		Len = len(queue)
		if Len == 1:
			print(queue[0].data, end=' ')
			queue = temp
			continue
		else:
			print(queue[0].data, queue[-1].data, end=' ')
			queue = temp
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)
		printCorner(root)
		print()


from collections import deque

def printCorner(root):
	a = deque()
	sum1 = 0
	b = []
	a.append(root)
	while len(a) != 0:
		n = len(a)
		for i in range(n):
			node = a.popleft()
			if i == 0 or i == n - 1:
				b.append(node.data)
			if node.left != None:
				a.append(node.left)
			if node.right != None:
				a.append(node.right)
	for i in range(len(b)):
		print(b[i], end=' ')
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)
		printCorner(root)
		print()


def level(root):
	q = []
	r = []
	if root == None:
		return
	q.append(root)
	while q:
		x = len(q)
		for i in range(x):
			n = q.pop(0)
			if i == 0:
				r.append(n.data)
			if x > 1 and i == x - 1:
				r.append(n.data)
			if n.left:
				q.append(n.left)
			if n.right:
				q.append(n.right)
	return r

def printCorner(root):
	x = level(root)
	for i in x:
		print(i, end=' ')


def printCorner(root):
	q = []
	a = []
	count = 0
	q.append(root)
	q.append(None)
	while q:
		t = q.pop(0)
		if t == None and q:
			q.append(None)
			count = 0
		elif t == None and (not q):
			break
		else:
			if t.left:
				q.append(t.left)
			if t.right:
				q.append(t.right)
			if count == 0 or q[0] == None:
				print(t.data, end=' ')
				count = 1
	return


def printCorner(root):
	(ans, q) = ([], [root])
	while q:
		cnt = len(q)
		for i in range(cnt):
			curr = q.pop(0)
			if i == 0:
				print(curr.data, end=' ')
			elif i == cnt - 1:
				print(curr.data, end=' ')
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
	return ans


def printCorner(root):
	if root is None:
		return None
	queue = []
	queue.append(root)
	while queue:
		n = len(queue)
		for i in range(n):
			if i == 0:
				x = queue.pop(0)
				print(x.data, end=' ')
			elif i == n - 1 and i != 0:
				x = queue.pop(0)
				print(x.data, end=' ')
			else:
				x = queue.pop(0)
			if x.left:
				queue.append(x.left)
			if x.right:
				queue.append(x.right)


def printCorner(root):
	if root is None:
		return []
	else:
		q = []
		final = []
		q.append(root)
		while q != []:
			size = len(q)
			level = []
			for i in range(size):
				cur = q.pop(0)
				level.append(cur.data)
				if cur.left != None:
					q.append(cur.left)
				if cur.right != None:
					q.append(cur.right)
			if len(level) >= 2:
				print(level[0], end=' ')
				print(level[-1], end=' ')
			else:
				print(level[0], end=' ')


def printCorner(root):
	if not root:
		return []
	queue = [root]
	res = []
	while queue:
		i = 0
		l = len(queue)
		while i < l:
			q = queue.pop(0)
			if i == 0 or i == l - 1:
				res.append(q.data)
			if q.left:
				queue.append(q.left)
			if q.right:
				queue.append(q.right)
			i += 1
	for ele in res:
		print(ele, end=' ')


def printCorner(root):
	res = []
	q = []
	q.append(root)
	while q:
		level = []
		l = len(q)
		for i in range(l):
			node = q.pop(0)
			if node:
				level.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if level:
			if len(level) == 1:
				print(level[0], end=' ')
			else:
				print(level[0], level[-1], end=' ')


def printCorner(root):
	from collections import deque
	q = deque([])
	q.append(root)
	bfs = []
	while len(q) != 0:
		lev = len(q)
		l = []
		for i in range(lev):
			cur = q.popleft()
			if i == 0 or i == lev - 1:
				print(cur.data, end=' ')
			l.append(cur.data)
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)


def printCorner(root):

	def traversal(root):
		q = deque([])
		q.append(root)
		list2 = []
		list1 = []
		while len(q) > 0:
			count = len(q)
			while count > 0:
				temp = q.popleft()
				list1.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				count -= 1
			if len(list1) == 1:
				list2.append(list1[0])
			else:
				list2.append(list1[0])
				list2.append(list1[-1])
			list1 = []
		for i in list2:
			print(i, end=' ')
	traversal(root)


def printCorner(root):
	ans = []
	l1 = [root]
	l2 = []
	while len(l1) != 0:
		for node in l1:
			if node.left != None:
				l2.append(node.left)
			if node.right != None:
				l2.append(node.right)
		if len(l1) > 1:
			ans.append(l1[0].data)
			ans.append(l1[len(l1) - 1].data)
		else:
			ans.append(l1[0].data)
		l1 = l2[:]
		l2 = []
	for i in ans:
		print(i, end=' ')


def printCorner(root):
	q = []
	q.append(root)
	print(q[0].data, end=' ')
	while len(q) > 0:
		s = len(q)
		while s > 0:
			node = q[0]
			if node.left != None:
				q.append(node.left)
			if node.right != None:
				q.append(node.right)
			q.pop(0)
			s -= 1
		if len(q) > 0:
			print(q[0].data, end=' ')
		if len(q) > 1:
			print(q[len(q) - 1].data, end=' ')


from collections import deque

def printCorner(root):
	q = deque()
	ans = []
	i = 0
	q.append(root)
	while len(q):
		n = len(q)
		if len(q) == 1:
			ans += [q[0].data]
		else:
			ans += [q[0].data, q[-1].data]
		for k in range(n):
			d = q.popleft()
			if d.left is not None:
				q.append(d.left)
			if d.right is not None:
				q.append(d.right)
	for i in ans:
		print(i, end=' ')


import collections

def printCorner(root):
	res = []
	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:
			res.append(level)
	for i in res:
		if len(i) < 2:
			print(i[0], end=' ')
		else:
			print(i[0], end=' ')
			print(i[-1], end=' ')


def printCorner(root):
	if root is None:
		return None
	else:
		q = []
		q.append(root)
		res = []
		while q:
			n = len(q)
			for i in range(n):
				node = q.pop(0)
				if i == 0 or i == n - 1:
					if node is not None:
						res.append(node.data)
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
		for resi in res:
			print(resi, end=' ')


from collections import deque

def printCorner(root):
	q = deque()
	q.append(root)
	while q:
		first = q[0]
		print(q[0].data, end=' ')
		for _ in range(len(q)):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if node != first:
			print(node.data, end=' ')