Given a binary tree, print nodes of extreme corners of each level but in alternate order.
Example:
For the above tree, the output is
1 2 7 8 31
– print rightmost node of 1st level
– print leftmost node of 2nd level
– print rightmost node of 3rd level
– print leftmost node of 4th level
– print rightmost node of 5th level
Example 1:
Input:
       1
     /  \
    2    3
Output: 1 2
Explanation: This represents a tree
with 3 nodes and 2 edges where root
is 1, left child of 1 is 3 and
right child of 1 is 2.
Your Task:
You don't have to take any input. Just complete the function ExtremeNodes() that takes root node as paramter  and return the answer (as vector in cpp, as ArrayList in Java, as list in python)
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ Number of nodes ≤ 100
1 ≤ Data of a node ≤ 1000

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Starter code:
class Solution:
    # Your task is to complete this function
    def ExtremeNodes(self, root):
        # Code here


Solutions:
class Solution:

	def ExtremeNodes(self, root):
		q = [root]
		ans = []
		dir = 0
		while len(q) > 0:
			l = len(q)
			for i in range(l):
				temp = q[0]
				q.pop(0)
				if dir == 0:
					if i == l - 1:
						ans.append(temp.data)
				elif i == 0:
					ans.append(temp.data)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
			dir ^= 1
		return ans


class Solution:

	def ExtremeNodes(self, root):
		q = [root]
		p = [1]
		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)
		ans = []
		for x in g:
			if x % 2 == 0:
				ans.append(g[x][0])
			else:
				ans.append(g[x][-1])
		return ans


class Solution:

	def ExtremeNodes(self, root):
		hash = {}
		m = [0] * 1

		def fun(root, level):
			if root == None:
				return
			m[0] = max(m[0], level)
			if level not in hash:
				hash[level] = [root.data]
			else:
				hash[level].append(root.data)
			fun(root.left, level + 1)
			fun(root.right, level + 1)
		fun(root, 0)
		ans = []
		for i in range(m[0] + 1):
			if i % 2 == 0:
				ans.append(hash[i][-1])
			else:
				ans.append(hash[i][0])
		return ans


class Solution:

	def ExtremeNodes(self, root):
		q = [root]
		ans = []
		flag = True
		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 flag:
				ans.append(lis[-1])
				flag = False
			else:
				ans.append(lis[0])
				flag = True
		return ans


class Solution:

	def ExtremeNodes(self, root):
		queue = [root, '\n']
		temp = []
		out = [[root.data]]
		while len(queue) > 1:
			if queue[0] == '\n':
				queue += ['\n']
				queue.pop(0)
				out.append(temp)
				temp = []
				continue
			if queue[0].left:
				temp += [queue[0].left.data]
				queue.append(queue[0].left)
			if queue[0].right:
				temp += [queue[0].right.data]
				queue.append(queue[0].right)
			queue.pop(0)
		res = []
		for i in range(len(out)):
			if i % 2 == 0:
				res.append(out[i][-1])
			else:
				res.append(out[i][0])
		return res


class Solution:

	def ExtremeNodes(self, root):
		q = []
		q.append(root)
		c = 1
		res = []
		res.append(root.data)
		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 c % 2 == 0:
					res.append(q[-1].data)
				else:
					res.append(q[0].data)
			c += 1
		return res


class Solution:

	def ExtremeNodes(self, root):
		(dl, dr) = ({}, {})

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

		def right_view(root, d):
			if root == None:
				return
			if d not in dr:
				dr[d] = root.data
			right_view(root.right, d + 1)
			right_view(root.left, d + 1)
		left_view(root, 0)
		right_view(root, 0)
		flag = 1
		sol = []
		for i in range(max(dl) + 1):
			if flag == 1:
				sol.append(dr[i])
				flag = 0
			else:
				sol.append(dl[i])
				flag = 1
		return sol


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		ans = []
		count = 0
		dq = deque()
		dq.append(root)
		while len(dq) > 0:
			currsize = len(dq)
			for i in range(currsize):
				temp = dq.popleft()
				if i == 0 and count % 2 == 1:
					ans.append(temp.data)
				if i == currsize - 1 and count % 2 == 0:
					ans.append(temp.data)
				if temp.left != None:
					dq.append(temp.left)
				if temp.right != None:
					dq.append(temp.right)
			count += 1
		return ans


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		toggle = False
		q = deque([root])
		ans = []
		while q:
			if toggle:
				ans.append(q[0].data)
			else:
				ans.append(q[-1].data)
			for _ in range(len(q)):
				x = q.popleft()
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)
			toggle ^= True
		return ans


class Solution:

	def ExtremeNodes(self, root):
		q = []
		q.append(root)
		ans = []
		k = 1
		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 k % 2 == 0:
				ans.append(lis[0])
			else:
				ans.append(lis[-1])
			k += 1
		return ans


class Solution:

	def ExtremeNodes(self, root):
		indi = 1
		li = []
		que = [root]
		li.append(root.data)
		indi = 1 - indi
		while que:
			ans = []
			for i in range(len(que)):
				node = que.pop(0)
				if node.left:
					que.append(node.left)
					ans.append(node.left.data)
				if node.right:
					que.append(node.right)
					ans.append(node.right.data)
			if indi == 1 and ans:
				li.append(ans[-1])
			elif indi == 0 and ans:
				li.append(ans[0])
			indi = 1 - indi
		return li


class Solution:

	def ExtremeNodes(self, root):
		dic = {}

		def recursive(root, lvl=1):
			nonlocal dic
			if root is None:
				return
			if lvl not in dic:
				dic[lvl] = root.data
			elif lvl & 1 == 1:
				dic[lvl] = root.data
			recursive(root.left, lvl + 1)
			recursive(root.right, lvl + 1)
		recursive(root)
		ans = []
		lvl = 1
		while lvl in dic:
			ans.append(dic[lvl])
			lvl += 1
		return ans


class Solution:

	def ExtremeNodes(self, root):
		ans = []
		level = 0
		if root is None:
			return []
		q = []
		q.append(root)
		while len(q) > 0:
			t = []
			level += 1
			if level % 2 == 0:
				ans.append(q[0].data)
			else:
				ans.append(q[-1].data)
			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
		return ans


class Solution:

	def ExtremeNodes(self, root):
		store = []
		self.helper(root, 0, store)
		output = []
		for i in range(len(store)):
			if i % 2:
				output.append(store[i][0])
			else:
				output.append(store[i][-1])
		return output

	def helper(self, root, level, store):
		if root is None:
			return
		if len(store) == level:
			store.append([])
		store[level].append(root.data)
		self.helper(root.left, level + 1, store)
		self.helper(root.right, level + 1, store)
		return


class Solution:

	def ExtremeNodes(self, root):
		if root is None:
			return []
		stack1 = [root]
		stack2 = []
		result = []
		count1 = 0
		count2 = 0
		while stack1 or stack2:
			while stack1:
				count2 = 0
				node = stack1.pop()
				if node.right is not None:
					stack2.append(node.right)
				if node.left is not None:
					stack2.append(node.left)
				if count1 == 0:
					result.append(node.data)
					count1 = 1
			while stack2:
				count1 = 0
				node = stack2.pop()
				if node.left is not None:
					stack1.append(node.left)
				if node.right is not None:
					stack1.append(node.right)
				if count2 == 0:
					result.append(node.data)
					count2 = 1
		return result


class Solution:

	def ExtremeNodes(self, root):
		lis = []
		l = 1
		q = [root]
		while q:
			res = []
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				res.append(node.data)
			if l % 2 == 0:
				lis.append(res[0])
			elif len(res) > 1:
				lis.append(res[-1])
			else:
				lis.append(res[0])
			l += 1
		return lis


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return []
		queue = deque([root])
		leftMost = False
		result = []
		while queue:
			if not leftMost:
				result.append(queue[-1].data)
			else:
				result.append(queue[0].data)
			leftMost = not leftMost
			for _ in range(len(queue)):
				node = queue.popleft()
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return result


class Solution:

	def ExtremeNodes(self, root):
		q = list()
		level = dict()
		q.append([root, 0])
		while q:
			(val, pos) = q.pop(0)
			level[pos] = level.get(pos, []) + [val.data]
			if val.left:
				q.append([val.left, pos + 1])
			if val.right:
				q.append([val.right, pos + 1])
		ans = list()
		ans.append(level[0][0])
		for i in range(1, 100):
			if level.get(i):
				if i & 1:
					ans.append(level.get(i)[0])
				else:
					ans.append(level.get(i)[-1])
			else:
				break
		return ans


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return
		q = deque([root])
		res = []
		flag = True
		flag2 = True
		while q:
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if flag2:
					res.append(root.data)
					flag2 = flag2 ^ 1
				elif not flag:
					if i == 0:
						res.append(node.data)
				elif i == n - 1:
					res.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			flag = flag ^ 1
		return res


class Solution:

	def ExtremeNodes(self, root):
		q = deque([])
		ans = [root.data]
		if root.left:
			q.append(root.left)
		if root.right:
			q.append(root.right)
		flag = True
		while q:
			size = len(q)
			if flag:
				ans.append(q[0].data)
			else:
				ans.append(q[-1].data)
			flag = not flag
			while size:
				t = q.popleft()
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
				size -= 1
		return ans


class Solution:

	def preorder(self, root, lvl, ht):
		if root is None:
			return
		if lvl in ht:
			ht[lvl].append(root.data)
		else:
			ht[lvl] = [root.data]
		self.preorder(root.left, lvl + 1, ht)
		self.preorder(root.right, lvl + 1, ht)

	def ExtremeNodes(self, root):
		ht = {}
		self.preorder(root, 0, ht)
		i = 0
		ans = []
		while i in ht:
			if i % 2 == 0:
				ans.append(ht[i][-1])
			else:
				ans.append(ht[i][0])
			i += 1
		return ans


class Solution:

	def ExtremeNodes(self, root):
		if root is None:
			return []
		q = [root]
		res = [root.data]
		flag = 1
		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:
				if flag == 1:
					res.append(nq[0].data)
				else:
					res.append(nq[-1].data)
			q = nq
			flag = 1 - flag
		return res


class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return []
		q = [root]
		ans = []
		f = 1
		while q:
			le = len(q)
			for i in range(le):
				t = q.pop(0)
				if f == 0 and i == 0:
					ans.append(t.data)
				if f == 1 and i == le - 1:
					ans.append(t.data)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			f = 1 - f
		return ans


class Solution:

	def ExtremeNodes(self, root):
		q = []
		q.append(root)
		q.append(-1)
		(m, l) = ([], [])
		m.append(root.data)
		k = 0
		while len(q) > 0:
			d = q.pop(0)
			if d and d != -1:
				if d.left:
					q.append(d.left)
					l.append(d.left.data)
				if d.right:
					q.append(d.right)
					l.append(d.right.data)
				if q[0] == -1:
					q.pop(0)
					q.append(-1)
					if len(l) > 0:
						if k == 0:
							k = -1
							m.append(l[0])
						else:
							k = 0
							m.append(l[-1])
					l = []
		return m


class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return []
		curr = [root]
		ans = []
		i = True
		while curr:
			next_level = []
			if i:
				ans.append(curr[-1].data)
			else:
				ans.append(curr[0].data)
			i = not i
			while curr:
				v = curr.pop(0)
				if v.left:
					next_level.append(v.left)
				if v.right:
					next_level.append(v.right)
			curr = next_level
		return ans


class Solution:

	def ExtremeNodes(self, root):
		q = []
		arr = []
		q.append(root)
		flag = 1
		while q:
			n = len(q)
			i = 0
			while i < n:
				r = q.pop(0)
				if r.left:
					q.append(r.left)
				if r.right:
					q.append(r.right)
				if not flag and i == 0 or (flag and i == n - 1):
					arr.append(r.data)
				i += 1
			flag = not flag
		return arr


class Solution:

	def ExtremeNodes(self, root):
		from collections import deque
		ans = []
		queue = deque([root])
		counter = 1
		while queue:
			count = len(queue)
			ls = []
			for i in range(count):
				curr = queue.popleft()
				ls.append(curr.data)
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			if counter % 2 == 0:
				ans.append(ls[0])
			else:
				ans.append(ls[-1])
			counter += 1
		return ans


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		ans = []
		q = deque()
		q.append(root)
		lv = 0
		while q:
			n = len(q)
			if lv == 1:
				ans.append(q[0].data)
			else:
				ans.append(q[-1].data)
			for i in range(n):
				nod = q.popleft()
				if nod.left:
					q.append(nod.left)
				if nod.right:
					q.append(nod.right)
			lv = (lv + 1) % 2
		return ans


class Solution:

	def ExtremeNodes(self, root):
		if root is None:
			return []
		res = []
		q = []
		q.append(root)
		level = 0
		right_to_left = True
		while q:
			level += 1
			temp = []
			for _ in range(len(q)):
				curr = q.pop(0)
				temp.append(curr.data)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			if right_to_left:
				res.append(temp[-1])
			else:
				res.append(temp[0])
			right_to_left = not right_to_left
		return res


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		queue = deque([root])
		level = 0
		result = []
		while queue:
			if level % 2 == 0:
				result.append(queue[-1].data)
			else:
				result.append(queue[0].data)
			for i in range(len(queue)):
				node = queue.popleft()
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			level += 1
		return result


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		if root is None:
			return []
		q = deque()
		q.append(root)
		ans = []
		cnt = 0
		while q:
			n = len(q)
			level = []
			cnt += 1
			for i in range(n):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				level.append(node.data)
			if cnt % 2 == 0:
				ans.append(level[0])
			else:
				ans.append(level[-1])
		return ans


class Solution:

	def ExtremeNodes(self, root):

		def helper(x):
			count = 0
			ans = []
			q = []
			t = []
			if not x:
				return ans
			q.append(x)
			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 count % 2 != 0:
					ans.append(t[0])
				else:
					ans.append(t[-1])
				t = []
				count += 1
			return ans
		a = helper(root)
		return a


class Solution:

	def ExtremeNodes(self, root):
		q = []
		q.append(root)
		ans = []
		while q:
			count = len(q)
			lst = []
			while count > 0:
				ele = q.pop(0)
				lst.append(ele.data)
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
				count -= 1
			ans.append(lst)
		lst = []
		for i in range(len(ans)):
			if i % 2 == 0:
				lst.append(ans[i][-1])
			else:
				lst.append(ans[i][0])
		return lst


class Solution:

	def ExtremeNodes(self, root):
		global a, m
		a = []
		m = -1

		def S(root, level):
			global a, m
			if not root:
				return 0
			if level > m:
				a.append([])
				m = level
			a[level].append(root.data)
			S(root.left, level + 1)
			S(root.right, level + 1)
		S(root, 0)
		k = []
		c = 1
		for i in a:
			if c % 2 != 0:
				k.append(i[-1])
			else:
				k.append(i[0])
			c = c + 1
		return k


class Solution:

	def ExtremeNodes(self, root):

		def height(root):
			if not root:
				return 0
			else:
				lheight = height(root.left)
				rheight = height(root.right)
				return max(lheight, rheight) + 1

		def currentLevel(root, level, arr, flag):
			if len(arr) == 1:
				return arr
			if not root:
				return
			else:
				if level == 1:
					arr.append(root.data)
				if level > 1:
					if flag == 'l':
						currentLevel(root.left, level - 1, arr, flag)
						currentLevel(root.right, level - 1, arr, flag)
					if flag == 'r':
						currentLevel(root.right, level - 1, arr, flag)
						currentLevel(root.left, level - 1, arr, flag)
				return arr
		res = []
		h = height(root)
		for i in range(1, h + 1):
			if i % 2 == 0:
				flag = 'l'
			else:
				flag = 'r'
			arr = currentLevel(root, i, [], flag)
			res.extend(arr)
		return res


class Solution:

	def ExtremeNodes(self, root):
		q = [root]
		newq = []
		ans = [[root.data]]
		while q or newq:
			node = q.pop(0)
			if node.left:
				newq.append(node.left)
			if node.right:
				newq.append(node.right)
			if not q:
				temp = []
				for ele in newq:
					temp += [ele.data]
				if temp:
					ans += [temp]
				q = newq
				newq = []
		fin = []
		ind = 0
		while ind < len(ans):
			fin += [ans[ind][-1]]
			ind += 1
			if ind < len(ans):
				fin += [ans[ind][0]]
				ind += 1
		return fin


class Solution:

	def ExtremeNodes(self, root):
		q = []
		q.append(root)
		q.append(None)
		res = []
		op = []
		while q:
			x = q.pop(0)
			if not x:
				if q:
					q.append(None)
					op.append(res)
					res = []
			else:
				res.append(x.data)
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)
		op.append(res)
		res = []
		k = 0
		for i in op:
			if k % 2 == 0:
				res.append(i[-1])
			else:
				res.append(i[0])
			k += 1
		return res


class Solution:

	def ExtremeNodes(self, root):
		h = {}

		def func(root, lvl):
			if not root:
				return
			h[lvl] = h.get(lvl, []) + [root.data]
			func(root.left, lvl + 1)
			func(root.right, lvl + 1)
			return
		func(root, 0)
		arr = []
		for i in range(len(h)):
			if i % 2 == 0:
				arr.append(h[i][-1])
			else:
				arr.append(h[i][0])
		return arr


class Solution:

	def ExtremeNodes(self, root):
		q = [root]
		lt = True
		res = []
		while len(q):
			l = n = len(q)
			lt = not lt
			i = 0
			while l:
				temp = q.pop(0)
				l -= 1
				i += 1
				if lt and i == 1:
					res.append(temp.data)
				if lt == False and i == n:
					res.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
		return res


class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return
		q = [root]
		res = []
		l = 0
		while q:
			temp = []
			for i in range(len(q)):
				cur = q.pop(0)
				temp.append(cur.data)
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
			if l % 2 == 0:
				res.append(temp[-1])
			else:
				res.append(temp[0])
			l += 1
		return res


class Solution:

	def ExtremeNodes(self, root):
		if root is None:
			return []
		else:
			import collections
			q = collections.deque()
			q.append(root)
			lst = []
			d = {}
			count = 0
			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)
				count = count + 1
				d[count] = level
			for key in list(d.keys()):
				if key % 2 == 0:
					lst.append(d[key][0])
				else:
					val = len(d[key]) - 1
					lst.append(d[key][val])
			return lst


class Solution:

	def ExtremeNodes(self, 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 range(0, len(ans)):
			if i % 2 == 0:
				fans.append(ans[i][-1])
			else:
				fans.append(ans[i][0])
		return fans


class Solution:

	def ExtremeNodes(self, root):
		a = []
		q = [root]
		c = 0
		while len(q):
			z = []
			l = len(q)
			while l:
				x = q[0]
				z.append(x)
				q = q[1:]
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)
				l -= 1
			if c == 0:
				c = 1
				a.append(z[-1].data)
			else:
				c = 0
				a.append(z[0].data)
		return a


class Solution:

	def ExtremeNodes(self, root):
		queue = []
		queue.append(root)
		flag = True
		res = []
		while len(queue) != 0:
			size = len(queue)
			if flag:
				flag = False
			else:
				flag = True
			if flag == True:
				res.append(queue[0].data)
			if flag == False:
				res.append(queue[size - 1].data)
			while size > 0:
				temp = queue[0]
				queue.pop(0)
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
				size -= 1
		return res


class Solution:

	def ExtremeNodes(self, root):
		(q1, q2) = ([], [root])
		ans = []
		lv = 1
		while q2:
			(q1, q2) = (q2, q1)
			q2.clear()
			if lv % 2:
				ans.append(q1[-1].data)
			else:
				ans.append(q1[0].data)
			lv += 1
			for nd in q1:
				if nd.left:
					q2.append(nd.left)
				if nd.right:
					q2.append(nd.right)
		return ans


class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return
		if not root.left and (not root.left):
			return [root.data]
		queue = []
		queue.append(root)
		a = []
		flag = 0
		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 flag:
				a.append(ans[0])
				flag = 0
			else:
				a.append(ans[-1])
				flag = 1
		return a


class Solution:

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

		def solve(root, depth):
			if root is None:
				return 0
			if len(res) == depth:
				res.append(root.data)
			elif depth % 2 != 0:
				res[depth] = res[depth]
			else:
				res[depth] = root.data
			solve(root.left, depth + 1)
			solve(root.right, depth + 1)
		solve(root, 0)
		return res


class Solution:

	def ExtremeNodes(self, root):
		q = []
		ans = []
		f = 0
		if root:
			q.append(root)
		while len(q) != 0:
			t = []
			n = len(q)
			while n:
				a = q.pop(0)
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
				t.append(a.data)
				n -= 1
			if f == 0:
				ans.append(t[-1])
				f = 1
			else:
				ans.append(t[0])
				f = 0
		return ans


from collections import *

class Solution:

	def ExtremeNodes(self, root):
		ans = []
		queue = deque()
		queue.append(root)
		flag = True
		while queue:
			l = []
			for _ in range(len(queue)):
				t = queue.popleft()
				l.append(t.data)
				if t.left:
					queue.append(t.left)
				if t.right:
					queue.append(t.right)
			if flag:
				ans.append(l[-1])
			else:
				ans.append(l[0])
			flag = not flag
		return ans


class Solution:

	def ExtremeNodes(self, 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)
		k = []
		for i in range(len(a)):
			if i == 0:
				k.append(a[i][0])
			elif i % 2 != 0:
				k.append(a[i][0])
			elif i % 2 == 0:
				k.append(a[i][-1])
		return k


class Solution:

	def ExtremeNodes(self, root):
		ans = []
		flag = 1
		queue = [root]
		while queue:
			if flag:
				ans.append(queue[-1].data)
				flag = 0
			else:
				ans.append(queue[0].data)
				flag = 1
			for i in range(len(queue)):
				cur = queue.pop(0)
				if cur.left:
					queue.append(cur.left)
				if cur.right:
					queue.append(cur.right)
		return ans


class Solution:

	def ExtremeNodes(self, root):
		q = [[root, 0]]
		c = 0
		d = -1
		while c != len(q):
			t = q[c][0]
			if q[c][1] > d:
				d = q[c][1]
			if t.left:
				q.append([t.left, q[c][1] + 1])
			if t.right:
				q.append([t.right, q[c][1] + 1])
			c += 1
		y = []
		for i in range(d + 1):
			if i % 2 == 0:
				l = c - 1
				r = -1
				s = -1
			else:
				l = 0
				r = c
				s = 1
			for j in range(l, r, s):
				if q[j][1] == i:
					y.append(q[j][0].data)
					break
		return y


class Solution:

	def ExtremeNodes(self, root):
		(que, l) = (deque([root]), 0)
		ans = []
		while que:
			n = len(que)
			for i in range(n):
				curr = que.popleft()
				if l % 2 == 0 and i == n - 1 or (l % 2 and i == 0):
					ans.append(curr.data)
				if curr.left:
					que.append(curr.left)
				if curr.right:
					que.append(curr.right)
			l += 1
		return ans


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		if root is None:
			return []
		q = deque()
		ans = deque()
		q.append(root)
		l = -1
		while q:
			n = len(q)
			te = n
			l += 1
			while n > 0:
				n -= 1
				t = q.popleft()
				if l % 2 == 1 and te - 1 == n:
					ans.append(t.data)
				elif l % 2 == 0 and n == 0:
					ans.append(t.data)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
		return ans


class Solution:

	def ExtremeNodes(self, root):
		queue = deque([root])
		ans = []
		while True:
			if not len(ans) or len(ans) & 1:
				ans.append(queue[0].data)
			else:
				ans.append(queue[-1].data)
			size = len(queue)
			while size:
				node = queue.popleft()
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
				size -= 1
			if not len(queue):
				break
		return ans
from collections import deque

class Node:

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

def PreOrder(root):
	if root is None:
		return
	print(root.data, end=' ')
	PreOrder(root.left)
	PreOrder(root.right)

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)
		nodes = Solution().ExtremeNodes(root)
		for node in nodes:
			print(node, end=' ')
		print()


class Solution:

	def ExtremeNodes(self, root):
		ans = []
		queue = []
		queue.append(root)
		flag = 1
		while queue:
			level = []
			for e in queue:
				if e.left:
					level.append(e.left)
				if e.right:
					level.append(e.right)
			if flag == 0:
				ans.append(queue[0].data)
				flag = 1
			else:
				ans.append(queue[-1].data)
				flag = 0
			queue.clear()
			queue = level.copy()
		return ans


class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return []
		if not root.left and (not root.right):
			return [root.data]
		level = 1
		mapp = {}
		self.getExtremeNodes(root, mapp, level)
		ans = [v for (k, v) in sorted(mapp.items())]
		return ans

	def getExtremeNodes(self, root, mapp, level):
		if not root:
			return
		if level not in mapp:
			mapp[level] = root.data
		elif level % 2 != 0:
			mapp[level] = root.data
		self.getExtremeNodes(root.left, mapp, level + 1)
		self.getExtremeNodes(root.right, mapp, level + 1)


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return []
		if not root.left and (not root.right):
			return [root.data]
		q = deque()
		q.append(root)
		ans = []
		level = 1
		while q:
			cur_size = len(q)
			if level % 2 == 0:
				ans.append(q[0].data)
			else:
				ans.append(q[-1].data)
			while cur_size > 0:
				node = q.popleft()
				cur_size -= 1
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		return ans


class Solution:

	def ExtremeNodes(self, root):
		if root is None:
			return []
		q = []
		q.append(root)
		final = []
		a = True
		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 a == True:
				final.append(level[-1])
			else:
				final.append(level[0])
			a = not a
		return final


class Solution:

	def ExtremeNodes(self, root):
		queue = [root]
		flag = 0
		ans = []
		while queue:
			n = len(queue)
			if flag == 1:
				ans.append(queue[0].data)
				flag = 0
			elif flag == 0:
				ans.append(queue[-1].data)
				flag = 1
			for i in range(n):
				a = queue.pop(0)
				if a.left:
					queue.append(a.left)
				if a.right:
					queue.append(a.right)
		return ans


class Solution:
	d = {}
	i = 0

	def ExtremeNodes(self, root):
		if root == None:
			return
		q = []
		ans = []
		q.append(root)
		flag = False
		while len(q) > 0:
			nodeCount = len(q)
			n = nodeCount
			while n > 0:
				n = n - 1
				curr = q[0]
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
				q.pop(0)
				if flag and n == nodeCount - 1:
					ans.append(curr.data)
				if not flag and n == 0:
					ans.append(curr.data)
			flag = not flag
		return ans


class Solution:

	def ExtremeNodes(self, root):
		(c, l) = (0, [root.data])
		q = []
		if root.left:
			q.append(root.left)
		if root.right:
			q.append(root.right)
		while q:
			cnt = len(q)
			for i in range(cnt):
				curr = q.pop(0)
				if i == 0:
					s = curr.data
				if i == cnt - 1:
					e = curr.data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			if c == 0:
				l.append(s)
			else:
				l.append(e)
			c = 1 - c
		return l


class Solution:

	def ExtremeNodes(self, root):
		r = []
		q = []
		q.append(root)
		while len(q) != 0:
			s = len(q)
			a = []
			for i in range(0, s, 1):
				temp = q[0]
				q.pop(0)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
				a.append(temp.data)
			r.append(a)
		result = []
		for i in range(0, len(r), 1):
			if i % 2 == 0:
				result.append(r[i][len(r[i]) - 1])
			else:
				result.append(r[i][0])
		return result


class Solution:

	def ExtremeNodes(self, root):
		q = []
		q.append(root)
		q.append(None)
		k = 0
		m = 0
		arr = []
		while q:
			t = q.pop(0)
			if not t and q:
				q.append(None)
				k = 1
				if m == 0:
					m = 1
				else:
					m = 0
			elif not t and (not q):
				break
			else:
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
				if not q[0] and m == 0:
					arr.append(t.data)
				if k == 1 and m == 1.0:
					arr.append(t.data)
					k = 0
		return arr


class Solution:

	def __init__(self):
		self.ans = []

	def solve(self, root):
		queue = [root]
		self.ans.append(root.data)
		child = []
		level = 1
		while len(queue) != 0:
			k = queue.pop(0)
			if k.left != None:
				child.append(k.left)
			if k.right != None:
				child.append(k.right)
			if len(queue) == 0:
				t = []
				for i in child:
					t.append(i.data)
				if len(child) != 0:
					if level % 2 == 1:
						self.ans.append(t[0])
					else:
						self.ans.append(t[-1])
				while len(child) != 0:
					queue.append(child.pop(0))
				level += 1

	def ExtremeNodes(self, root):
		self.solve(root)
		return self.ans


from collections import defaultdict

class Solution:

	def traversal(self, root, dic, l):
		if root == None:
			return
		dic[l].append(root.data)
		self.traversal(root.left, dic, l + 1)
		self.traversal(root.right, dic, l + 1)

	def ExtremeNodes(self, root):
		dic = defaultdict(list)
		self.traversal(root, dic, 0)
		ans = [root.data]
		for i in range(1, len(dic)):
			if i % 2 == 0:
				ans.append(dic[i][-1])
			else:
				ans.append(dic[i][0])
		return ans


class Solution:

	def ExtremeNodes(self, root):
		ans = []
		l1 = [root]
		l2 = []
		k = 0
		while len(l1) != 0:
			for node in l1:
				if node.left != None:
					l2.append(node.left)
				if node.right != None:
					l2.append(node.right)
			t = [l1[0], l1[len(l1) - 1]]
			if k % 2 != 0:
				ans.append(t[0].data)
			else:
				ans.append(t[1].data)
			k += 1
			l1 = l2[:]
			l2 = []
		return ans


class Solution:

	def ExtremeNodes(self, root):
		q = []
		a = []
		q.append(root)
		a.append(root.data)
		x = 0
		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:
				if x == 0:
					a.append(q[0].data)
					x = 1
				else:
					a.append(q[-1].data)
					x = 0
		return a


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		q = deque()
		ans = []
		i = 0
		q.append(root)
		while len(q):
			n = len(q)
			if len(q) == 1:
				ans += [q[0].data]
			elif i % 2 == 0:
				ans += [q[-1].data]
			else:
				ans += [q[0].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)
			i += 1
		return ans


class Solution:

	def ExtremeNodes(self, 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 != None:
					q.append(p.left)
				if p.right != None:
					q.append(p.right)
				count = count - 1
			l.append(sl)
		count = 0
		al = []
		al.append(l[0][0])
		for i in range(1, len(l)):
			if count % 2 == 0:
				al.append(l[i][0])
			else:
				al.append(l[i][-1])
			count += 1
		return al


class Solution:

	def ExtremeNodes(self, root):
		arr = []
		queue = [root]
		left = False
		while queue:
			l = len(queue)
			i = 0
			while i < l:
				q = queue.pop(0)
				if left and i == 0:
					arr.append(q.data)
				elif not left and i == l - 1:
					arr.append(q.data)
				if q.left:
					queue.append(q.left)
				if q.right:
					queue.append(q.right)
				i += 1
			left = not left
		return arr


class Solution:

	def ExtremeNodes(self, root):
		a = []
		cl = -1
		q = [(root, 0)]
		while q:
			(c, l) = q.pop(0)
			if l % 2 and l > cl or (l % 2 == 0 and (not q or q[0][1] > l)):
				a.append(c.data)
			if l > cl:
				cl = l
			for b in (c.left, c.right):
				if b:
					q.append((b, l + 1))
		return a


class Solution:

	def ExtremeNodes(self, root):
		q = []
		q.append(root)
		l = []
		while len(q):
			l1 = []
			for i in range(len(q)):
				c = q.pop(0)
				l1.append(c.data)
				if c.left:
					q.append(c.left)
				if c.right:
					q.append(c.right)
			l.append(l1)
		ans = []
		for i in range(len(l)):
			if i % 2 == 0:
				ans.append(l[i][-1])
			else:
				ans.append(l[i][0])
		return ans


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		if root == None:
			return
		q = deque([])
		ans = []
		q.append(root)
		f = True
		while len(q) > 0:
			n = len(q)
			st = []
			for i in range(1, n + 1):
				temp = q.popleft()
				st.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			if f:
				ans.append(st[-1])
			else:
				ans.append(st[0])
			f = not f
		return ans


class Solution:

	def ExtremeNodes(self, root):
		queue = []
		result = []
		queue.append(root)
		lr = False
		while queue:
			row = []
			for i in range(len(queue)):
				node = queue.pop(0)
				if node:
					row.append(node.data)
					queue.append(node.left)
					queue.append(node.right)
			if row:
				if lr:
					result.append(row[0])
				else:
					result.append(row[-1])
				lr = not lr
		return result


class Solution:

	def ExtremeNodes(self, root):
		ans = []
		q = []
		q.append(root)
		q.append(None)
		is_right = True
		is_new_level = True
		while len(q) > 1:
			e = q.pop(0)
			if e is not None and q[0] is None and is_right and is_new_level:
				is_new_level = False
				is_right = False
				ans.append(e.data)
			if e is None:
				q.append(None)
				is_new_level = True
				continue
			if not is_right and is_new_level:
				ans.append(e.data)
				is_new_level = False
				is_right = True
			if e.left is not None:
				q.append(e.left)
			if e.right is not None:
				q.append(e.right)
		return ans


class Solution:

	def ExtremeNodes(self, root):
		if not root:
			return []
		if root.left is None and root.right is None:
			return [root.data]
		extreme = [root.data]
		queue = [root]
		left = True
		while queue:
			newLevel = []
			for node in queue:
				if node.left:
					newLevel.append(node.left)
				if node.right:
					newLevel.append(node.right)
			queue.clear()
			if newLevel:
				if left:
					extreme.append(newLevel[0].data)
				else:
					extreme.append(newLevel[-1].data)
				queue.extend(newLevel)
			left = not left
		return extreme


class Solution:

	def ExtremeNodes(self, root):
		ans = []
		queue = []
		front = 0
		queue.append(root)
		while len(queue) > 0:
			n = len(queue)
			for i in range(n):
				elem = queue.pop(0)
				if i == 0 or i == n - 1:
					if front == True and i == 0:
						ans.append(elem.data)
					if front == False and i == n - 1:
						ans.append(elem.data)
				if elem.left:
					queue.append(elem.left)
				if elem.right:
					queue.append(elem.right)
			front = not front
		return ans


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		(ans, direc) = ([], 1)
		q = deque([root])
		while q:
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if direc == 0 and i == 0:
					ans.append(node.data)
				if direc == 1 and i == n - 1:
					ans.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			direc = 1 - direc
		return ans


import sys
sys.setrecursionlimit(10000)

class Solution:

	def ExtremeNodes(self, root):
		nodes = []
		if root is None:
			return nodes
		q = []
		q.append(root)
		flag = False
		while q != []:
			nc = len(q)
			n = nc
			while n != 0:
				n -= 1
				curr = q[0]
				if curr.left is not None:
					q.append(curr.left)
				if curr.right is not None:
					q.append(curr.right)
				q.pop(0)
				if flag and n == nc - 1:
					nodes.append(curr.data)
				if not flag and n == 0:
					nodes.append(curr.data)
			flag = not flag
		return nodes


class Solution:

	def ExtremeNodes(self, root):
		c = deque()
		a = 0
		j = []
		c.append(root)
		while c:
			l = len(c)
			h = []
			for i in range(l):
				q = c.popleft()
				if q.left:
					c.append(q.left)
				if q.right:
					c.append(q.right)
				h.append(q.data)
			if a % 2 == 0:
				j.append(h[len(h) - 1])
			else:
				j.append(h[0])
			a += 1
		return j


class Solution:

	def ExtremeNodes(self, root):
		lev = 1
		ans = []
		q = [root]
		while q:
			n = len(q)
			for i in range(n):
				curr = q.pop(0)
				if lev % 2 == 0:
					if i == 0:
						ans.append(curr.data)
				elif i == n - 1:
					ans.append(curr.data)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			lev += 1
		return ans


class Solution:

	def ExtremeNodes(self, root):
		arr = []
		q = []
		q.append(root)
		c = 0
		flag = True
		while q:
			n = len(q)
			for i in range(n):
				temp = q[0]
				q.pop(0)
				if c == 0 and flag:
					if i == n - 1:
						arr.append(temp.data)
						c = 1
						flag = False
				elif c == 1 and flag:
					if i == 0:
						arr.append(temp.data)
						c = 0
						flag = False
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			flag = True
		return arr


class Solution:

	def ExtremeNodes(self, root):
		q = [root]
		ind = 0
		res = []
		while q:
			n = len(q)
			ans = None
			for i in range(n):
				if not ans:
					if ind % 2 == 0:
						ans = q[-1].data
					else:
						ans = q[0].data
				p = q.pop(0)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
			res.append(ans)
			ind += 1
		return res


class Solution:

	def ExtremeNodes(self, root):
		q = deque()
		q.append(root)
		count = 0
		res = []
		while q:
			size = len(q)
			count += 1
			if count % 2 == 0:
				res.append(q[0].data)
			else:
				res.append(q[-1].data)
			for i in range(size):
				tmp = q.popleft()
				if tmp.left:
					q.append(tmp.left)
				if tmp.right:
					q.append(tmp.right)
		return res


class Solution:

	def ExtremeNodesUtil(self, root, dic, level):
		if root == None:
			return
		if level == 0:
			dic[0] = root.data
		elif level % 2 == 0:
			dic[level] = root.data
		elif level % 2 == 1:
			if level not in dic:
				dic[level] = root.data
		self.ExtremeNodesUtil(root.left, dic, level + 1)
		self.ExtremeNodesUtil(root.right, dic, level + 1)

	def ExtremeNodes(self, root):
		dic = {}
		res = []
		self.ExtremeNodesUtil(root, dic, 0)
		for i in sorted(dic.keys()):
			res.append(dic[i])
		return res


from collections import deque

class Solution:

	def ExtremeNodes(self, root):
		q = deque([])
		out = []
		q.append(root)
		f = True
		while len(q):
			k = len(q)
			if f:
				out.append(q[-1].data)
			else:
				out.append(q[0].data)
			while k:
				t = q.popleft()
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
				k -= 1
			f = not f
		return out