Given a binary tree of size N, find all the nodes at odd levels.Root is considered at level 1.
Example 1:
Input: 
          1
       /     \
      2       3
    /   \       \
   4     5       6
        /  \     /
       7    8   9
Output  1 4 5 6
Example 2:
Input: 
             1
      /      \
     2        3
   /   \    /   \
  4     5  6     7
         
Output: 1 4 5 6 7
Your Task:
You don't need to read input or print anything. Your task is to complete the function nodesAtOddLevels() which takes root node of the tree as input parameter and returns an list of all the nodes at odd levels in preorder.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= Number of nodes <= 10^{3}
1 <= Data of a node <= 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self,val):
        self.data=val
        self.left=None
        self.right=None
'''
class Solution:
    def nodesAtOddLevels(self,root):
        #code here

Solutions:
class Solution:

	def nodesAtOddLevels(self, root):
		q = [root]
		res = []
		lev = 1
		while q:
			l = len(q)
			for i in range(l):
				p = q.pop(0)
				if lev % 2 != 0:
					res.append(p.data)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
			lev += 1
		return res


from collections import deque

class Solution:

	def nodesAtOddLevels(self, root):
		queue = deque()
		queue.append(root)
		ans_list = []
		level = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				curr = queue.popleft()
				if level % 2 != 0:
					ans_list.append(curr.data)
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
		return ans_list


class Solution:

	def nodesAtOddLevels(self, root):
		return findNodes(root, [], 1)

def findNodes(root, res, l):
	if root == None:
		return res
	if l % 2 == 1:
		res.append(root)
	findNodes(root.left, res, l + 1)
	findNodes(root.right, res, l + 1)
	return res


class Solution:

	def nodesAtOddLevels(self, root):
		if node is None:
			return
		if k == 0:
			print(node.data)
			k = l
			return
		else:
			odd_level(node.left, k - 1, l)
			odd_level(node.right, k - 1, l)


class Solution:

	def fun(self, root, level, l):
		if root == None:
			return
		if level >= len(l):
			l.append([])
		l[level].append(root.data)
		self.fun(root.left, level + 1, l)
		self.fun(root.right, level + 1, l)

	def nodesAtOddLevels(self, root):
		l = []
		self.fun(root, 0, l)
		t = []
		for i in range(len(l)):
			if i % 2 == 0:
				t.extend(l[i])
		return t


class Solution:

	def solve(self, root, dic, l):
		if root == None:
			return
		if l % 2 != 0:
			dic.append(root.data)
		l += 1
		self.solve(root.left, dic, l)
		self.solve(root.right, dic, l)
		l -= 1

	def nodesAtOddLevels(self, root):
		dic = []
		self.solve(root, dic, 1)
		return dic


class Solution:

	def getNodesFromOddLevel(self, root, level: int=1):
		if root is None:
			return []
		elif level % 2:
			return [root.data] + self.getNodesFromOddLevel(root.left, level + 1) + self.getNodesFromOddLevel(root.right, level + 1)
		else:
			return self.getNodesFromOddLevel(root.left, level + 1) + self.getNodesFromOddLevel(root.right, level + 1)

	def nodesAtOddLevels(self, root):
		return self.getNodesFromOddLevel(root, 1)


class Solution:

	def nodesAtOddLevels(self, root):
		values = []
		queue = [root]
		count = 0
		while queue:
			count += 1
			level = []
			for i in queue:
				if i == None:
					continue
				if count % 2 != 0:
					values.append(i.data)
				level.append(i.left)
				level.append(i.right)
			queue = level
		return values


class Solution:

	def nodesAtOddLevels(self, root):
		q = [root]
		count = 1
		list = []
		while q:
			if count % 2 != 0:
				for i in q:
					list.append(i.data)
			for _ in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return list


class Solution:

	def nodesAtOddLevels(self, root):

		def levelOrder(self, root):

			def height(node):
				if node is None:
					return 0
				else:
					lheight = height(node.left)
					rheight = height(node.right)
					if lheight > rheight:
						return lheight + 1
					else:
						return rheight + 1

			def currlvl(root, lvl):
				if root is None:
					return
				elif lvl % 2 != 0:
					res.append(root.data)
				elif lvl > 1:
					currlvl(root.left, lvl - 1)
					currlvl(root.right, lvl - 1)
			res = []
			h = height(root)
			for i in range(1, h + 1):
				currlvl(root, i)
			return res


class Solution:

	def getNod(self, root, arr, lev):
		if not root:
			return
		if lev % 2 != 0:
			arr.append(root.data)
		self.getNod(root.left, arr, lev + 1)
		self.getNod(root.right, arr, lev + 1)

	def nodesAtOddLevels(self, root):
		arr = []
		self.getNod(root, arr, 1)
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		return lll(root, 1, [])

	def lll(self, root, l, arr):
		if root is None:
			return
		if l % 2:
			arr.append(root.data)
		lll(root.left, l + 1, arr)
		lll(root.rihjt, l + 1, arr)
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		n = root
		arr = []
		stack = [n]
		while stack:
			n = stack.pop()
			if n is not None:
				arr.append(n.data)
				stack.append(n.right)
				stack.append(n.left)
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return []
		q = []
		q.append(root)
		counter = 0
		ans = []
		while len(q) > 0:
			counter += 1
			t = []
			while len(q) != 0:
				x = st.pop(0)
				if x.left is not None:
					t.append(x.left)
				if x.right is not None:
					t.append(x.right)
				if counter % 2 != 0:
					ans.append(x.data)
			q = t
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		q = []
		q.append(root)
		arr = []
		x = 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 x == 1:
				arr.extend(lis)
				x = 0
			elif x == 0:
				x = 1
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		c = 1
		s1 = []
		queue = [root]
		while queue != []:
			t = []
			for i in range(len(queue)):
				curr = queue[0]
				t.append(curr.data)
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
				queue.pop(0)
			if c % 2 == 1:
				s1.extend(t)
				c += 1
			elif c % 2 != 1:
				c += 1
		return s1


class Solution:

	def nodesAtOddLevels(self, root):
		d = []
		q = []
		g = {}
		if root == None:
			ans = []
			return ans
		d.append(root)
		q.append(0)
		while len(d) > 0:
			c = d.pop(0)
			m = q.pop(0)
			if m not in g:
				g[m] = [c.data]
			else:
				g[m].append(c.data)
			if c.left != None:
				d.append(c.left)
				q.append(m + 1)
			if c.right != None:
				d.append(c.right)
				q.append(m + 1)
		l = []
		for x in g:
			if x % 2 != 0:
				for i in range(0, len(g[x])):
					l.append(g[x][i])
		return l


class Solution:

	def nodesAtOddLevels(self, root):
		queue = deque([(root, 1)])
		l = []
		while queue:
			(node, h) = queue.popleft()
			if node.left is None and node.right is None and (h % 2 == 1):
				l.append(node.data)
			if node.left is not None:
				queue.append((node.left, h + 1))
			if node.right is not None:
				queue.append((node.right, h + 1))
		return l


class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return
		q = [root]
		res = []
		flag = 1
		while len(q) != 0:
			root = q.pop(0)
			if flag % 2 != 0:
				res.append(root.data)
			flag += 1
			if root.left:
				q.append(root.left)
			if root.right:
				q.append(root.right)
		return res


class Solution:

	def depthOfOddLeaf(self, root):
		arr = []
		level = 1
		q = []
		q.append(root)
		while len(q) != 0:
			for i in range(len(q)):
				node = q.pop(0)
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
				if level % 2 == 1:
					arr.append(level)
			level += 1
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		q = []
		q.append(root)
		ans = []
		p = 1
		while len(q):
			count = len(q)
			while count > 0:
				p = q.pop(0)
				if p % 2 == 1:
					ans.append(p.data)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				count -= 1
			p += 1
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		if not root:
			return []
		stack = [root]
		ans = []
		level = 1
		while stack:
			temp = []
			for i in range(len(stack)):
				node = stack.pop(0)
				if node.left:
					stack.append(node.left)
				if node.right != None:
					stack.append(node.right)
				temp.append(node.data)
			if temp != [] and level % 2 == 1:
				ans.append(temp)
			level += 1
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		global a
		a = []

		def sol(root, level):
			global a
			if root:
				if level % 2 == 0:
					a.append(root.data)
				sol(root.left, level + 1)
				sol(root.right, level + 1)
		sol(root, 0)
		return a


class Solution:

	def nodesAtOddLevels(self, root):
		q = []
		odd = []
		q.append(root)
		q.append('$')
		level = 1
		while len(q) > 0:
			t = q.pop(0)
			if level % 2 != 0:
				odd.append(t.data)
			if t == '$':
				if len(q) > 0:
					q.append('$')
					level += 1
			else:
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return odd


class Solution:

	def nodesAtOddLevels(self, root):
		arr = []
		self.myFunc(root, arr, 0)
		return arr

	def myFunc(self, root, arr, level):
		if not root:
			return
		level += 1
		if level % 2:
			arr.append(root.data)
		self.myFunc(root.left, arr, level)
		self.myFunc(root.right, arr, level)
		return


class Solution:

	def __init__(self):
		self.level = {}

	def trav(self, root, l):
		if l in self.level:
			self.level[l].append(root.data)
		elif l % 2 == 1:
			self.level[l] = [root.data]
		if root.left != None:
			self.trav(root.left, l + 1)
		if root.right != None:
			self.trav(root.right, l + 1)

	def nodesAtOddLevels(self, root):
		self.trav(root, 1)
		res = []
		for l in self.level.keys():
			res.extend(self.level[l])
		return res


class Solution:

	def nodesAtOddLevels(self, root):
		d = {}
		level = 0
		self.helper(root, level, d)
		d1 = sorted(d.keys(), key=lambda x: x % 2 != 0)
		print(d1)

	def helper(self, root, level, d):
		if not root:
			return
		if level not in d:
			d[level] = [root.data]
		else:
			d[level].append(root.data)
		self.helper(root.left, level + 1, d)
		self.helper(root.right, level + 1, d)


class Solution:

	def nodesAtOddLevels(self, root):
		output = []

		def oddLevel(root, level):
			if root == None:
				return
			if level % 2 != 0:
				output.append(root.data)
			oddLevel(root.left)
			oddLevel(root.right)
		oddLevel(root, 1)
		return output


class Node:

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

class Solution:

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

		def func(root, level):
			if root is None:
				return
			if level % 2 != 0:
				res.append(root.data)
			func(root.left, level + 1)
			func(root.right, level + 1)
		func(root, 1)
		return res
x = Solution()
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(7)
root.left.right.right = Node(8)
root.right.right = Node(6)
root.right.right.left = Node(9)
x.nodesAtOddLevels(root)


class Solution:

	def nodesAtOddLevels(self, root):

		def helper(x):
			ans = []
			q = []
			t = []
			if not x:
				return ans
			q.append(x)
			while q:
				l = len(q)
				for i in range(l):
					a = q.pop(0)
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t.append(a.data)
				ans.append(t)
				t = []
			return ans
		a = helper(root)
		answer = []
		for i in range(len(a)):
			if i % 2 == 0:
				b = a[i]
				for j in b:
					answer.append(j)
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		q = []
		v = []
		q.append(root)
		l = 1
		while q != []:
			n = len(q)
			for i in range(n):
				temp = q.pop(0)
				if i % 2 == 1:
					v.append(temp)
				if temp.left:
					v.append(temp.left)
				if temp.right:
					v.append(temp.right)
			l += 1
		return v


class Solution:

	def nodesAtOddLevels(self, root):
		level = 1
		queue = [root]
		result = []
		while queue:
			size = len(queue)
			level += 1
			for i in range(size):
				node = node.pop(0)
				if node.left != None:
					queue.append(node.left)
				if node.right != None:
					queue.append(node.right)
				if level > 1 and level % 2 != 0:
					result.append(node.data)
		return result


class Solution:

	def nodesAtOddLevels(self, root):
		sum2 = 0
		if root is None:
			return sum2
		hight = self.TreeHight(root)
		i = 1
		lst = []
		while i <= hight:
			if i % 2 != 0:
				lst = self.LevelOrdertrvsl(root, i, lst)
			i += 1
		return lst

	def LevelOrdertrvsl(self, root, level, lst):
		if root is None:
			return lst
		if level == 1:
			lst.append(root.data)
			return lst
		elif level > 1:
			lst = self.LevelOrdertrvsl(root.left, level - 1, lst)
			lst = self.LevelOrdertrvsl(root.right, level - 1, lst)
		return lst

	def TreeHight(self, root):
		if root is None:
			return 0
		ls = 1 + self.TreeHight(root.left)
		rs = 1 + self.TreeHight(root.right)
		maxh = max(ls, rs)
		return maxh


class Solution:

	def nodesAtOddLevels(self, root):
		if root == None:
			return None
		q = [root]
		ans = []
		k = 0
		while len(q) > 0:
			k += 1
			count = len(q)
			for i in range(count):
				temp = q.pop(0)
				if k % 2 != 0:
					ans.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		ans = []
		i = 0
		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 i % 2 == 0:
				ans += l
			queue = level
			level = []
			i += 1
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		L = []
		if root == None:
			return
		if isOdd:
			L.append(root.data)
		printOddNodes(root.left, not isOdd)
		printOddNodes(root.right, not isOdd)
		return L


class Solution:

	def nodesAtOddLevels(self, root):
		s = {}
		c = 0
		q = [[root, 0]]
		m = -1
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			if g % 2 == 0:
				if g in s:
					s[g].append(t.data)
				else:
					s[g] = [t.data]
			if g > m:
				m = g
			if t.left:
				q.append([t.left, g + 1])
			if t.right:
				q.append([t.right, g + 1])
			c += 1
		l = []
		i = 0
		while i <= m:
			l.extend(s[g])
			i += 2
		return l


class Solution:

	def nodesAtOddLevels(self, root):
		if not root:
			return
		l = []
		odd = True
		if odd:
			l.append(root.data)
		self.nodesAtOddLevels(root.left, not odd)
		self.nodesAtOddLevels(root.right, not odd)
		return l


class Node:

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

class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return []
		else:
			import collections
			q = collections.deque()
			q.append(root)
			lst = []
			count = 1
			while q:
				for i in range(len(q)):
					node = q.popleft()
					if node and count % 2 != 0:
						lst.append(node.data)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				count = count + 1
			return lst


class Solution:

	def nodesAtOddLevels(self, root):
		arr = []
		if not root:
			return arr
		q = []
		q.append(root)
		f = 0
		while q:
			if f == 0:
				arr += [x.data for x in q]
			for x in range(len(q)):
				t = q.pop(0)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			f = 1 - f
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		q = deque()
		q.append(root)
		(ans, level) = ([], 0)
		while q:
			level += 1
			n = len(q)
			for _ in range(n):
				p = q.popleft()
				if level % 2 == 1:
					ans.append(p.data)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		level = 1
		ans = []
		queue = [root]
		while queue:
			for _ in range(len(queue)):
				cur = queue.pop(0)
				if cur.left:
					queue.append(cur.left)
				if cur.right:
					queue.append(cur.right)
				if level % 2 == 1:
					arr.append(cur.data)
			level += 1
		return arr
from collections import deque

class Node:

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

class Solution:

	def nodesAtOddLevels(self, root):
		oddNodes = []
		self.nodesAtOddLevelsUtil(root, 1, oddNodes)
		return oddNodes

	def nodesAtOddLevelsUtil(self, root, l, oddNodes):
		if root == None:
			return
		if l % 2 == 1:
			oddNodes.append(root)
		self.nodesAtOddLevelsUtil(root.left, l + 1, oddNodes)
		self.nodesAtOddLevelsUtil(root.right, l + 1, oddNodes)

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__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.nodesAtOddLevels(root)
		v = []
		for node in res:
			v.append(node.data)
		v.sort()
		for i in v:
			print(i, end=' ')
		print()


import queue

class Solution:

	def nodesAtOddLevels(self, root):
		if root == None:
			return []
		ans = []
		q = queue.Queue()
		q.put((root, 1))
		while not q.empty():
			size = q.qsize()
			li = []
			for i in range(size):
				(temp, lvl) = q.get()
				li.append(temp.data)
				if temp.left:
					q.put((temp.left, lvl + 1))
				if temp.right:
					q.put((temp.right, lvl + 1))
			for i in range(size):
				if lvl % 2 != 0:
					ans.append(li[i])
		return ans
from collections import deque

class Node:

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

class Solution:

	def nodesAtOddLevels(self, root):
		oddNodes = []
		self.nodesAtOddLevelsUtil(root, 1, oddNodes)
		return oddNodes

	def nodesAtOddLevelsUtil(self, root, l, oddNodes):
		if root == None:
			return
		if l % 2 == 1:
			oddNodes.append(root)
		self.nodesAtOddLevelsUtil(root.left, l + 1, oddNodes)
		self.nodesAtOddLevelsUtil(root.right, l + 1, oddNodes)

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__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.nodesAtOddLevels(root)
		v = []
		for node in res:
			v.append(node.data)
		v.sort()
		for i in v:
			print(i, end=' ')
		print()


def printOddLevels(root, lvl, res):
	if root == None:
		return
	if lvl % 2 != 0:
		res.append(root)
	printOddLevels(root.left, lvl + 1, res)
	printOddLevels(root.right, lvl + 1, res)

class Solution:

	def nodesAtOddLevels(self, root):
		res = []
		printOddLevels(root, 1, res)


class Solution:

	def nodesAtOddLevels(self, root):
		oddnodes = []
		q = []
		q.append(root)
		n = 1
		while q:
			n = len(q)
			for i in range(n):
				temp = q.pop(0)
				if k % 2 == 1:
					oddnodes.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			k += 1
		return


from collections import deque

class Solution:

	def nodesAtOddLevels(self, r):
		(q, ret) = (deque([r, 1]), [])
		if not r:
			return ret
		while q:
			(n, l) = q.popleft()
			if n.left:
				q += ((n.left, l + 1),)
			if n.right:
				q += ((n.right, l + 1),)
			if l & 1:
				ret += (n.data,)
		return ret


class Solution:

	def nodesAtOddLevels(self, root):
		stack = []
		stack.append(root)
		ans = []
		while stack:
			n = len(stack)
			j = 1
			level = []
			for i in range(n):
				node = stack.pop()
				level.append(node.data)
				if node.left:
					stack.append(node.left)
				if node.right:
					stack.append(node.right)
			if j % 2 != 0:
				for i in level:
					ans.append(i)
			j += 1
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		self.findlevel(root, True)

	def findlevel(root, isOdd):
		if root == None:
			return
		if isOdd:
			print(root.data, end=' ')
		self.findlevel(root.left, not isOdd)
		self.findlevel(root.right, not isOdd)


import collections

class Solution:

	def nodesAtOddLevels(self, 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)
		odd_nodes = []
		for i in range(len(res)):
			if i % 2 == 0:
				odd_nodes.append(res[i])
		flat_list = [x for xs in odd_nodes for x in xs]
		return flat_list


from collections import deque

class Solution:

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


class Solution:

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


class Solution:

	def nodesAtOddLevels(self, root):
		ans = []
		queue = []
		queue.append(root)
		while len(queue) > 0:
			elem = queue.pop(0)
			ans.append(elem.data)
			if elem.left:
				queue.append(elem.left)
			if elem.right:
				queue.append(elem.right)
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		currentlevel = []
		nextlevel = []
		if root == None:
			return 0
		currentlevel.append(root)
		level = 1
		ans = []
		while len(currentlevel) > 0:
			curr = currentlevel.pop(0)
			if curr.left:
				nextlevel.append(curr.left)
			if curr.right:
				nextlevel.append(curr.right)
			if len(currentlevel) == 0:
				(currentlevel, nextlevel) = (nextlevel, currentlevel)
				if level % 2 != 0:
					ans = ans + currentlevel
				level += 1
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		q = [root]
		i = 0
		ans = []
		flag = True
		while q:
			n = len(q)
			while n:
				temp = q.pop(0)
				if flag:
					ans.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				n -= 1
			flag = not flag
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		a = [root]
		ans = []
		level = 0
		while a:
			level += 1
			n = len(a)
			for i in range(n):
				p = a.pop(0)
				if level % 2 != 0:
					ans.append(p)
				if p.left:
					a.append(p.left)
				if p.right:
					a.append(p.right)
		return ans


class Solution:

	def nodesAtOddLevels(self, root):
		vals = []
		idx = 1
		q.append(root)
		while q:
			node = q.pop(0)
			if node is not None:
				if idx % 2 == 1:
					vals.append(node.data)
			if node.left is not None:
				q.append(node.left)
			if node.right is not None:
				q.append(node.right)
			idx += 1
		return vals


class Solution:

	def nodesAtOddLevels(self, root):
		res = []
		ans = []

		def traverse(root, level):
			if root == None:
				return
			if level < len(res):
				res[level].append(root.data)
			else:
				res.append([root.data])
			traverse(root.left, level + 1)
			traverse(root.right, level + 1)
		traverse(root, 0)
		for i in range(len(res)):
			if i % 2 == 0:
				for j in range(len(res[i])):
					ans.append(res[i][j])
		return ans


from collections import deque

class Node:

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

class queue:

	def __init__(self):
		self.lists = deque()
		self.size = 0

	def enqueue(self, data):
		self.lists.append(data)
		self.size += 1

	def dequeue(self):
		if self.size == 0:
			return -1
		else:
			temp = self.lists.popleft()
			self.size -= 1
			return temp

	def isempty(self):
		return self.size == 0
q = queue()

class Solution:

	def nodesAtOddLevels(self, root):
		level_count = 1
		l = []
		if root == None:
			return l
		else:
			q.enqueue(root)
			while q.isempty() != True:
				count = q.size
				while count > 0:
					temp = q.dequeue
					if level_count % 2 == 1:
						l.append(temp.data)
					if temp.left:
						q.enqueue(temp.left)
					if temp.right:
						q.enqueue(temp.right)
					count -= 1
				level_count += 1
			return l


class Solution:

	def nodesAtOddLevels(self, root):
		l = 1
		s = [root]
		ans = []
		while len(s):
			n = len(s)
			for i in range(n):
				temp = s.pop(0)
				if l % 2 != 0:
					ans.append(temp.data)
				if temp.left:
					s.append(temp.left)
				if temp.right:
					s.append(temp.right)
			l += 1
		return ans


from collections import deque

class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return 0
		q.append(root)
		q.append(None)
		level = 1
		arr = []
		while len(q) > 0:
			cur = q.popleft()
			if cur != None:
				if level % 2 != 0:
					arr.append(cur.data)
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
			elif len(q) > 0:
				q.append(None)
				level += 1
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		q = deque()
		q.append(root)
		q.append(None)
		arr = []
		level = 1
		while len(q) > 0:
			node = q.popleft()
			if node is not None:
				if level % 2 != 0:
					arr.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			elif len(q) > 0:
				q.append(None)
				level += 1
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return self.l
		final = []
		q = []
		q.append(root)
		level = 1
		while len(q):
			s = len(q)
			for i in range(s):
				l = q.pop(0)
				if level % 2 == 1:
					final.append(l)
				if l.left:
					q.append(l.left)
				if l.right:
					q.append(l.right)
			l += 1
		return final


class Solution:

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

	def addnode(self, node, level):
		if root is None:
			return
		if level % 2 == 1:
			self.l.append(node)
		self.addnode(node.left, level + 1)
		self.addnode(node.right, level + 1)

	def nodesAtOddLevels(self, root):
		if root is None:
			return self.l
		self.addnode(root, 1)
		return self.l


class Solution:

	def helper(self, d, q):
		while len(q) != 0:
			(p, l) = q.pop(0)
			if l % 2 != 0:
				if l not in d:
					d[l] = []
				d[l].append(root.data)
			if root.left:
				q.append((root.left, l + 1))
			if root.right:
				q.append((root.right, l + 1))
		return d

	def nodesAtOddLevels(self, root):
		if not root:
			return []
		if not root.left and root.right:
			return root.data
		d = {}
		d = self.helper(d, [(root, 1)])
		l = []
		for i in sorted(d):
			l += i
		return l


class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return []
		d = defaultdict(list)

		def bfs(node, level):
			if not node:
				return
			d[level].append(node.data)
			bfs(node.left, level + 1)
			bfs(node.right, level + 1)
		bfs(root, 0)
		ans = []
		for (key, value) in d.items():
			if key % 2 != 0:
				ans.append(value)
		return ans


class Solution:

	def nodesAtOddLevelsUtil(self, root, level):
		if root is None:
			if level % 2 == 0:
				print(root.data)
			self.nodesAtOddLevelsUtil(root.left, level + 1)
			self.nodesAtOddLevelsUtil(root.left, level + 1)

	def nodesAtOddLevels(self, root):
		level = 1
		self.nodesAtOddLevelsUtil(root, self.evel)


class Solution:

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

	def nodesAtOddLevels(self, root):
		level = 1
		self.traverse(root, level)
		return self.res

	def traverse(self, root, level):
		if root == None:
			return
		if level % 2 != 0:
			self.res.append(root.data)
		self.traverse(root.left, level + 1)
		self.taverse(root.right, level + 1)
		return


class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return
		q = []
		q.append(root)
		res = []
		oddNodes(root, True)

		def oddNodes(root, isOdd):
			if root is None:
				return
			n = q.pop(0)
			if isOdd:
				res.append(n.data)
			if n.left:
				q.append(n.left)
				oddNodes(n.left, not isOdd)
			if n.right:
				q.append(n.right)
				oddNodes(n.right, not isOdd)
		return res


class Solution:

	def nodesAtOddLevels(self, root):
		q = []
		q.append(root)
		lev = 1
		l = []
		while len(q) > 0:
			n = q.pop(0)
			if lev % 2 != 0:
				l.append(n.data)
			if n.left:
				q.append(n.left)
				lev += 1
			if n.right:
				q.append(n.right)
				lev += 1
		return l


class Solution:

	def nodesAtOddLevels(self, root):
		ans = []
		q = [root]
		while q:
			node = q.pop()
			size = len(node)
			for i in range(size):
				ans.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return ans


class Solution:

	def nodesAtOddLevels(self, root):

		def height(root):
			if root == None:
				return 0
			left = height(root.left)
			right = height(root.right)
			return max(left, right) + 1

		def traversal(root, level):
			if root == None:
				return None
			if level == 0:
				list1.append(root.data)
			else:
				traversal(root.left, level - 1)
				traversal(root.right, level - 1)
		tall = height(root)
		count = 1
		list1 = []
		for i in range(tall):
			if count % 2 != 1:
				traversal(root, i)
		return list1


class Solution:

	def helper(self, root, lst):
		if root is None:
			return
		lst.append(root.data)
		self.helper(root.left.left, lst)
		self.helper(root.left.right, lst)
		self.helper(root.right.left, lst)
		self.helper(root.right.right, lst)
		return lst

	def nodesAtOddLevels(self, root):
		lst = []
		self.helper(root, lst)
		return lst


class Solution:

	def nodesAtOddLevels(self, root):
		ans = []

		def sol(r, val):
			nonlocal ans
			if r == None:
				return
			if len(ans) > val:
				ans[val] += 1
			else:
				ans.append(1)
			sol(r.left, val + 1)
			sol(r.right, val + 1)
		sol(root, 0)
		rans = []
		for i in range(len(ans)):
			if (i + 1) % 2 != 0:
				rans.append(ans[i])
		return rans


class Solution:

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

	def _traverse(self, root, h):
		if root:
			if h % 2:
				self.ans.append(root.data)
			self._traverse(root.left, h + 1)
			self._traverse(root.right, h + 1)

	def nodesAtOddLevels(self, root):
		self._traverse(root, 1)
		return self.ans


def FindOddLevelNode(root, ht, ans):
	if root == None:
		return
	if ht & 1 == 1:
		ans.append(root.data)
	FindOddLevelNode(root.left, ht + 1, ans)
	FindOddLevelNode(root.right, ht + 1, ans)

class Solution:

	def nodesAtOddLevels(self, root):
		ht = 1
		ans = []
		FindOddLevelNode(root, ht, ans)
		return ans


su = 0

class Solution:

	def no(self, root, p):
		global su
		if root == None:
			return
		if p % 2 != 0:
			su = su + root.data
		self.no(root.left, p, su)
		self.no(root.right, p, su)

	def nodesAtOddLevels(self, root):
		self.no(root, 1, 0)
		global su
		return su


from collections import deque

class Solution:

	def nodesAtOddLevels(self, root):
		level = 0
		q = deque()
		q.append(root)
		ans = []
		while q:
			level += 1
			size = len(q)
			while size:
				ele = q.popleft()
				if level % 2:
					ans.append(ele.data)
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
				size -= 1
		return ans


import queue

class Solution:

	def nodesAtOddLevels(self, root):
		if root is None:
			return []
		q = queue.Queue()
		q.put(root)
		arr = []
		i = 1
		while q.empty() != True:
			size = q.qsize()
			while size > 0:
				current_node = q.get()
				if i % 2 != 0:
					arr.append(current_node.data)
				if current_node.left != None:
					q.put(current_node.left)
				if current_node.right != None:
					q.put(current_node.right)
				size -= 1
			i += 1
		return arr


class Solution:

	def nodesAtOddLevels(self, root):
		q = []
		temp = []
		q.append(root)
		level = 1
		while len(q) > 0:
			count = len(q)
			for i in range(count):
				node = q.pop(0)
				if level % 2 == 0:
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				else:
					if node.left:
						q.append(node.left)
						temp.append(node.left)
					if node.right:
						q.append(node.right)
						temp.append(node.right)
			level = level + 1
		return temp


class Solution:

	def nodesAtOddLevels(self, root):
		level = 0
		if root is None:
			return []
		q = []
		res = []
		q.append(root)
		while len(q) > 0:
			level += 1
			temp = []
			while len(q) > 0:
				node = q.pop(0)
				if level % 2 == 1:
					res.append(node.data)
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			q = temp
		return res