Complete the function to find spiral order traversal of a tree. For below tree, function should return 1, 2, 3, 4, 5, 6, 7.
 
 
Example 1:
Input:
      1
    /   \
   3     2
Output:1 3 2
Example 2:
Input:
           10
         /     \
        20     30
      /    \
    40     60
Output: 10 20 30 60 40 
Your Task:
The task is to complete the function findSpiral() which takes root node as input parameter and returns the elements in spiral form of level order traversal as a list. The newline is automatically appended by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
0 <= Number of nodes <= 10^{5}
0 <= Data of a node <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Complete search

Starter code: #User function Template for python3


#Function to return a list containing the level order traversal in spiral form.
def findSpiral(root):
    # Code here




Solutions:
def findSpiral(root):
	order = []
	if not root:
		return order
	(ltr, rtl) = ([], [])
	rtl.append(root)
	while ltr or rtl:
		while rtl:
			popped = rtl.pop()
			order.append(popped.data)
			if popped.right:
				ltr.append(popped.right)
			if popped.left:
				ltr.append(popped.left)
		while ltr:
			popped = ltr.pop()
			order.append(popped.data)
			if popped.left:
				rtl.append(popped.left)
			if popped.right:
				rtl.append(popped.right)
	return order


def findSpiral(root):
	if root is None:
		a = []
		return a
	ans = [[]]
	q = []
	q.append(root)
	count = 0
	while len(q) > 0:
		n = len(q)
		count += 1
		arr = []
		for i in range(n):
			temp = q.pop(0)
			arr.append(temp.data)
			if temp.left is not None:
				q.append(temp.left)
			if temp.right is not None:
				q.append(temp.right)
		ans.append(arr)
	result = []
	count = False
	for arr in ans:
		if count == False:
			for item in arr:
				result.append(item)
		else:
			for i in range(len(arr) - 1, -1, -1):
				result.append(arr[i])
		count = not count
	return result


def findSpiral(root):
	if root == None:
		return []
	else:
		nodes = [root]
		ans = []
		while len(nodes):
			temp = []
			add = []
			for i in nodes:
				if i.left:
					temp.append(i.left)
				if i.right:
					temp.append(i.right)
				add.append(i.data)
			ans.append(add)
			nodes = temp.copy()
		flag = True
		final = []
		for arr in ans:
			if not flag:
				for i in arr:
					final.append(i)
			else:
				new = arr[::-1]
				for i in new:
					final.append(i)
			flag = bool(1 - flag)
		return final


def findSpiral(root):
	if root == None:
		return []
	flag = 1
	queue = []
	ans = []
	q = []
	q.append(root)
	while q:
		level = []
		if not flag:
			for i in range(len(q)):
				temp = q.pop(0)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
				level.append(temp.data)
			ans = ans + level
		else:
			for i in range(len(q)):
				temp = q.pop(0)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
				level.append(temp.data)
			ans = ans + level[::-1]
		flag = not flag
	return ans


c = 2

def findSpiral(root):
	if root is None:
		return []
	s1 = []
	s2 = []
	s1.append(root)
	result = []
	while len(s1) != 0 or len(s2) != 0:
		while len(s1) != 0:
			temp = s1[-1]
			s1.pop()
			result.append(temp.data)
			if temp.right:
				s2.append(temp.right)
			if temp.left:
				s2.append(temp.left)
		while len(s2) != 0:
			temp = s2[-1]
			s2.pop()
			result.append(temp.data)
			if temp.left:
				s1.append(temp.left)
			if temp.right:
				s1.append(temp.right)
	return result


def findSpiral(root):
	if root is None:
		return []
	start = root
	q = []
	level = 0
	q.append(root)
	ans = []
	while q:
		level += 1
		total = len(q)
		t = []
		while total:
			val = q.pop(0)
			t.append(val.data)
			if val.left:
				q.append(val.left)
			if val.right:
				q.append(val.right)
			total -= 1
		if level & 1:
			ans += t[::-1]
		else:
			ans += t
	return ans


def findSpiral(root):
	if not root:
		return []
	q = [root]
	res = []
	j = 1
	while q:
		le = len(q)
		t = []
		for i in range(le):
			a = q.pop(0)
			t.append(a.data)
			if a.left:
				q.append(a.left)
			if a.right:
				q.append(a.right)
		if j % 2 == 0:
			res = res + t
		else:
			t = t[::-1]
			res = res + t
		j += 1
	return res
	return res


def findSpiral(root):
	q = []
	q.append(root)
	ans = []
	count = 0
	while q:
		l = []
		for x in range(0, len(q)):
			cur = q[0]
			q.remove(cur)
			if cur:
				l.append(cur.data)
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
		if count % 2 == 0:
			ans += l[::-1]
		else:
			ans += l
		count += 1
	return ans


def findSpiral(root):

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

	def prin(root, le, ltr, a):
		if root is None:
			return
		if le == 1:
			a.append(root.data)
		elif le > 1:
			if ltr:
				prin(root.left, le - 1, ltr, a)
				prin(root.right, le - 1, ltr, a)
			else:
				prin(root.right, le - 1, ltr, a)
				prin(root.left, le - 1, ltr, a)
	h = height(root)
	ltr = False
	a = []
	for i in range(1, h + 1):
		prin(root, i, ltr, a)
		ltr = not ltr
	return a


def findSpiral(root):
	itr = False
	h = height(root)
	for i in range(1, h + 1):
		pri(root, i, itr)
		itr = not itr
	return []

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

def pri(node, level, itr):
	if node is None:
		return
	if level == 1:
		print(node.data, end=' ')
	elif level > 1:
		if itr:
			pri(node.left, level - 1, itr)
			pri(node.right, level - 1, itr)
		else:
			pri(node.right, level - 1, itr)
			pri(node.left, level - 1, itr)
	return


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

def findSpiral(root):
	lst = []
	h = height(root)
	flag = True
	for i in range(1, h + 1):
		spiraltraversal(root, i, flag)
		flag = not flag
	return lst

def spiraltraversal(root, level, flag):
	if root is None:
		return
	if level == 1:
		print(root.data, end=' ')
	elif level > 1:
		if not flag:
			spiraltraversal(root.left, level - 1, flag)
			spiraltraversal(root.right, level - 1, flag)
		else:
			spiraltraversal(root.right, level - 1, flag)
			spiraltraversal(root.left, level - 1, flag)


from collections import deque

def findSpiral(root):
	ans = []
	if root is None:
		return ans
	queue = deque()
	queue.append(root)
	reverse = True
	while len(queue) != 0:
		level = []
		size = len(queue)
		for i in range(size):
			top = queue[0]
			queue.popleft()
			level.append(top.data)
			if top.left is not None:
				queue.append(top.left)
			if top.right is not None:
				queue.append(top.right)
		if reverse:
			level = reversed(level)
		reverse = not reverse
		ans += level
	return ans


def findSpiral(root):
	stack = []
	result = []
	if root:
		stack.append(root)

	def findSpiralUtil(node):
		nonlocal stack, result
		flag = True
		while stack:
			length1 = len(stack)
			res = []
			for i in range(length1):
				element = stack.pop(0)
				if element.left:
					stack.append(element.left)
				if element.right:
					stack.append(element.right)
				res.append(element.data)
			if not flag:
				for i in res:
					result.append(i)
			else:
				for i in res[::-1]:
					result.append(i)
			flag = not flag
		return result
	return findSpiralUtil(root)


def findSpiral(root):
	if root == None:
		return []
	q = []
	q.append(root)
	ans = []
	flg = 1
	while len(q) != 0:
		size = len(q)
		tmp = []
		while size != 0:
			curr = q.pop(0)
			tmp.append(curr.data)
			if curr.left != None:
				q.append(curr.left)
			if curr.right != None:
				q.append(curr.right)
			size -= 1
		if flg % 2 != 0:
			tmp = tmp[::-1]
		for i in tmp:
			ans.append(i)
		flg += 1
	return ans


def findSpiral(root):
	if root is None:
		return []
	q = [root]
	ans = [root.data]
	count = 0
	while len(q) != 0:
		size = len(q)
		for i in range(size):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if count % 2 == 0:
			for i in range(len(q)):
				ans.append(q[i].data)
		else:
			for i in range(len(q) - 1, -1, -1):
				ans.append(q[i].data)
		count += 1
	return ans


def findSpiral(root):
	s1 = []
	s2 = []
	L = []
	if root is None:
		return L
	s1 = [root]
	while len(s1) > 0 or len(s2) > 0:
		while len(s1) > 0:
			elem = s1.pop()
			L.append(elem.data)
			if elem.right is not None:
				s2.append(elem.right)
			if elem.left is not None:
				s2.append(elem.left)
		while len(s2) > 0:
			elem = s2.pop()
			L.append(elem.data)
			if elem.left is not None:
				s1.append(elem.left)
			if elem.right is not None:
				s1.append(elem.right)
	return L


def findSpiral(root):
	res = []
	q = []
	q.append(root)
	invert = True
	while q:
		level = []
		qlen = len(q)
		for i in range(qlen):
			node = q.pop(0)
			if node:
				level.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if level:
			if invert:
				res += level[::-1]
				invert = not invert
			else:
				res += level
				invert = not invert
	return res


def findSpiral(root):
	if not root:
		return []
	result = []
	s1 = [root]
	s2 = []
	flag = True
	while s1 or s2:
		while s1:
			node = s1.pop()
			result.append(node.data)
			if node.right:
				s2.append(node.right)
			if node.left:
				s2.append(node.left)
		while s2:
			node = s2.pop()
			result.append(node.data)
			if node.left:
				s1.append(node.left)
			if node.right:
				s1.append(node.right)
	return result


def findSpiral(root):
	if not root:
		return []
	queue = [[root]]
	ans = [root.data]
	flag = 0
	while queue:
		level = queue.pop(0)
		temp = []
		for node in level:
			if node.left:
				temp.append(node.left)
			if node.right:
				temp.append(node.right)
		if temp:
			queue.append(temp)
			if flag:
				ans += list(reversed([node.data for node in temp]))
				flag = 0
			else:
				ans += [node.data for node in temp]
				flag = 1
	return ans


def findSpiral(root):
	if root is None:
		return []
	(s1, s2, arr) = ([], [], [])
	s1.append(root)
	while len(s1) != 0 or len(s2) != 0:
		if len(s1) > 0:
			while len(s1) > 0:
				temp = s1.pop()
				arr.append(temp.data)
				if temp.right:
					s2.append(temp.right)
				if temp.left:
					s2.append(temp.left)
		if len(s2) > 0:
			while len(s2) > 0:
				temp = s2.pop()
				arr.append(temp.data)
				if temp.left:
					s1.append(temp.left)
				if temp.right:
					s1.append(temp.right)
	return arr


from collections import deque

def findSpiral(root):
	if root == None:
		return []
	q = deque()
	q.append(root)
	res = []
	c = 0
	while len(q):
		n = len(q)
		ans = []
		for i in range(n):
			p = q.popleft()
			ans.append(p.data)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
		if c % 2 == 0:
			ans = ans[::-1]
			res.extend(ans[:])
		else:
			res.extend(ans[:])
		c += 1
	return res


from collections import deque

def findSpiral(root):
	queue = deque()
	result = []
	if not root:
		return result
	stack = []
	queue.append(root)
	alternate = True
	while queue:
		size = len(queue)
		if alternate:
			for i in range(size):
				temp = queue.popleft()
				result.append(temp.data)
				if temp.right:
					stack.append(temp.right)
				if temp.left:
					stack.append(temp.left)
			alternate = False
		else:
			for i in range(size):
				temp = queue.popleft()
				result.append(temp.data)
				if temp.left:
					stack.append(temp.left)
				if temp.right:
					stack.append(temp.right)
			alternate = True
		while stack:
			queue.append(stack.pop())
	return result


def findSpiral(root):
	if root is None:
		return []
	res = []
	stack = [root]
	left = False
	while stack:
		tmp_stack = []
		for _ in range(len(stack)):
			temp = stack.pop()
			res.append(temp.data)
			if left:
				if temp.left:
					tmp_stack.append(temp.left)
				if temp.right:
					tmp_stack.append(temp.right)
			else:
				if temp.right:
					tmp_stack.append(temp.right)
				if temp.left:
					tmp_stack.append(temp.left)
		stack = tmp_stack
		left = not left
	return res


def findSpiral(root):
	if root == None:
		return []
	s1 = []
	s2 = []
	ans = []
	s1.append(root)
	while not len(s1) == 0 or not len(s2) == 0:
		while not len(s1) == 0:
			temp = s1[-1]
			s1.pop()
			ans.append(temp.data)
			if temp.right:
				s2.append(temp.right)
			if temp.left:
				s2.append(temp.left)
		while not len(s2) == 0:
			temp = s2[-1]
			s2.pop()
			ans.append(temp.data)
			if temp.left:
				s1.append(temp.left)
			if temp.right:
				s1.append(temp.right)
	return ans


def findSpiral(root):
	if root == None:
		return []
	queue = []
	queue.append(root)
	ans = []
	level = 1
	while len(queue) != 0:
		size = len(queue)
		temp = []
		while size != 0:
			curr = queue.pop(0)
			temp.append(curr.data)
			if curr.left != None:
				queue.append(curr.left)
			if curr.right != None:
				queue.append(curr.right)
			size -= 1
		if level % 2 != 0:
			temp = temp[::-1]
		for i in temp:
			ans.append(i)
		level += 1
	return ans


def findSpiral(root):
	if root is None:
		return []
	ans = []
	queue = [root]
	flag = True
	while len(queue) != 0:
		n = len(queue)
		level = []
		for i in range(n):
			node = queue[0]
			queue.pop(0)
			level.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		flag = not flag
		if flag == False:
			level = level[::-1]
		for i in range(n):
			ans.append(level[i])
	return ans


def findSpiral(root):

	def helper(root, mp, k):
		if root:
			if k in mp:
				mp[k].append(root.data)
			else:
				mp[k] = [root.data]
			helper(root.left, mp, k + 1)
			helper(root.right, mp, k + 1)
		return mp
	mp = helper(root, {}, 0)
	ans = []
	dir = 1
	for i in mp:
		if dir == 0:
			ans.extend(mp[i])
			dir = 1
		else:
			ans.extend(mp[i][::-1])
			dir = 0
	return ans


def findSpiral(root):
	res = []
	s1 = []
	s2 = []
	s1.append(root)
	while len(s1) != 0 or len(s2) != 0:
		while len(s1) != 0:
			node = s1.pop()
			if node:
				res.append(node.data)
				if node.right:
					s2.append(node.right)
				if node.left:
					s2.append(node.left)
		while len(s2) != 0:
			node = s2.pop()
			if node:
				res.append(node.data)
				if node.left:
					s1.append(node.left)
				if node.right:
					s1.append(node.right)
	return res


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


def findSpiral(root):
	dic = {}
	q = deque(list())
	q.append([root, 0])
	size = 1
	while size > 0:
		temp = q[0][0]
		l = q[0][1]
		q.popleft()
		size -= 1
		if temp != None:
			if l not in dic.keys():
				dic[l] = list()
			dic[l].append(temp.data)
			q.append([temp.left, l + 1])
			q.append([temp.right, l + 1])
			size += 2
	q = ''
	ans = list()
	for i in dic.keys():
		if i % 2 != 0:
			ans.extend(dic[i])
		else:
			ans.extend(reversed(dic[i]))
		dic[i] = ''
	return ans


def findSpiral(root):
	res = []

	def height(root):
		if not root:
			return 0
		else:
			l = height(root.left)
			r = height(root.right)
			if l > r:
				return l + 1
			else:
				return r + 1

	def levelspriral(root, level, ltr):
		if root is None:
			return
		if level == 1:
			res.append(root.data)
		elif level > 1:
			if ltr:
				levelspriral(root.left, level - 1, ltr)
				levelspriral(root.right, level - 1, ltr)
			else:
				levelspriral(root.right, level - 1, ltr)
				levelspriral(root.left, level - 1, ltr)

	def printspiral(root):
		h = height(root)
		ltr = False
		for i in range(1, h + 1):
			levelspriral(root, i, ltr)
			ltr = not ltr
	printspiral(root)
	return res


def findSpiral(root):
	if root is None:
		return []
	result = []
	frontier = [root]
	level = 0
	while frontier:
		nextFrontier = []
		i = len(frontier) - 1
		if level % 2 == 0:
			temp = []
			while i >= 0:
				temp.insert(0, frontier[i].data)
				if frontier[i].left is not None:
					nextFrontier.append(frontier[i].left)
				if frontier[i].right is not None:
					nextFrontier.append(frontier[i].right)
				i -= 1
			result.extend(temp)
		else:
			temp = []
			while i >= 0:
				temp.insert(0, frontier[i].data)
				if frontier[i].right is not None:
					nextFrontier.append(frontier[i].right)
				if frontier[i].left is not None:
					nextFrontier.append(frontier[i].left)
				i -= 1
			result.extend(temp)
		frontier = nextFrontier
		level += 1
	return result


def findSpiral(root):
	if root is None:
		return []
	queue = []
	ans = []
	queue.append(root)
	counter = 0
	while len(queue) > 0:
		counter += 1
		level = []
		for i in range(len(queue)):
			root = queue[0]
			queue.pop(0)
			if root.left:
				queue.append(root.left)
			if root.right:
				queue.append(root.right)
			level.append(root.data)
		if counter % 2 == 0:
			ans.extend(level)
		else:
			ans.extend(level[::-1])
	return ans


def findSpiral(root):
	q = []
	ans = []
	if root == None:
		return ans
	q.append(root)
	i = 1
	while q:
		n = len(q)
		a = []
		for j in range(0, n):
			node = q.pop(0)
			a.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if i % 2 == 0:
			for k in a:
				ans.append(k)
		else:
			for k in a[::-1]:
				ans.append(k)
		i += 1
	return ans


import collections
from collections import deque

def findSpiral(root):
	ans = []
	if root is None:
		return ans
	queue = collections.deque()
	queue.append(root)
	while queue:
		currSize = len(queue)
		currList = []
		while currSize > 0:
			currNode = queue.popleft()
			currList.append(currNode.data)
			currSize -= 1
			if currNode.left is not None:
				queue.append(currNode.left)
			if currNode.right is not None:
				queue.append(currNode.right)
		ans.append(currList)
	res = ans.pop(0)
	while len(ans) > 1:
		res.extend(ans.pop(0))
		res.extend(ans.pop(0)[::-1])
	if ans:
		res.extend(ans[0])
	return res


from collections import deque

def findSpiral(root):
	if not root:
		return []
	res = []
	que = deque([root])
	rightToLeft = False
	while que:
		temp = []
		rightToLeft = not rightToLeft
		for _ in range(len(que)):
			node = que.popleft()
			if node:
				temp.append(node.data)
				que.append(node.left)
				que.append(node.right)
		if temp:
			if rightToLeft:
				temp.reverse()
			res += temp
	return res


import queue

def findSpiral(root):
	if not root:
		return []
	result = []
	lr = queue.LifoQueue()
	rl = queue.LifoQueue()
	rl.put(root)
	while not lr.empty() or not rl.empty():
		while not lr.empty():
			current_node = lr.get()
			result.append(current_node.data)
			if current_node.left:
				rl.put(current_node.left)
			if current_node.right:
				rl.put(current_node.right)
		while not rl.empty():
			current_node = rl.get()
			result.append(current_node.data)
			if current_node.right:
				lr.put(current_node.right)
			if current_node.left:
				lr.put(current_node.left)
	return result


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

def printLevel(result, node, lvl, flg):
	if node is None:
		return
	if lvl == 1:
		result.append(node.data)
	elif lvl > 1:
		if flg is True:
			printLevel(result, node.left, lvl - 1, flg)
			printLevel(result, node.right, lvl - 1, flg)
		else:
			printLevel(result, node.right, lvl - 1, flg)
			printLevel(result, node.left, lvl - 1, flg)

def findSpiral(root):
	result = []
	if root is None:
		return result
	h = height(root)
	ltr = False
	for i in range(1, h + 1):
		printLevel(result, root, i, ltr)
		ltr = not ltr
	return result


from collections import deque

def findSpiral(root):
	resultentlist = list()
	dQ = deque()
	if root != None:
		dQ.append(root)
	level = 1
	while dQ:
		listing = list()
		times = len(dQ)
		while times:
			holdnode = dQ.popleft()
			listing.append(holdnode.data)
			if holdnode.left != None:
				dQ.append(holdnode.left)
			if holdnode.right != None:
				dQ.append(holdnode.right)
			times -= 1
		if level % 2 == 1:
			listing.reverse()
		resultentlist.extend(listing)
		level += 1
	return resultentlist


def findSpiral(root):
	s1 = []
	s2 = []
	ans = []
	if root == None:
		return []
	s1.append(root)
	while len(s1) != 0 or len(s2) != 0:
		while len(s1) != 0:
			temp = s1[-1]
			ans.append(temp.data)
			s1.pop()
			if temp.right:
				s2.append(temp.right)
			if temp.left:
				s2.append(temp.left)
		while len(s2) != 0:
			temp = s2[-1]
			ans.append(temp.data)
			s2.pop()
			if temp.left:
				s1.append(temp.left)
			if temp.right:
				s1.append(temp.right)
	ans = [i for i in ans]
	return ans


def findSpiral(root):
	if not root:
		return []
	queue = [root]
	ans = []
	while queue:
		k = []
		for i in range(len(queue)):
			m = queue.pop(0)
			k.append(m.data)
			if m.left is not None:
				queue.append(m.left)
			if m.right is not None:
				queue.append(m.right)
		ans.append(k)
	for i in range(len(ans)):
		if i % 2 == 0:
			ans[i] = ans[i][::-1]
	lst = []
	for i in ans:
		for j in i:
			lst.append(j)
	return lst


def findSpiral(root):
	if root is None:
		return []
	level_elements = [root]
	elements_values_list = []
	number_of_elements = 1
	reverse_flag = True
	while number_of_elements > 0:
		level_elements_list = []
		while number_of_elements:
			element = level_elements.pop(0)
			number_of_elements -= 1
			if element.left:
				level_elements.append(element.left)
			if element.right:
				level_elements.append(element.right)
			level_elements_list.append(element.data)
		if reverse_flag:
			level_elements_list.reverse()
		elements_values_list += level_elements_list
		reverse_flag = not reverse_flag
		number_of_elements = len(level_elements)
	return elements_values_list


def findSpiral(root):
	_d = {}
	solve(root, 0, _d)
	_res = []
	for (key, val) in _d.items():
		if key % 2 == 0:
			val.reverse()
		_res.extend(val)
	return _res

def solve(root, level, _d):
	if not root:
		return _d
	try:
		_d[level].append(root.data)
	except Exception as e:
		_d[level] = [root.data]
	solve(root.left, level + 1, _d)
	solve(root.right, level + 1, _d)


import copy

def findSpiral(root):
	flag = 0
	if root == None:
		return []
	queue = [root]
	res = []
	while len(queue):
		l = len(queue)
		flag = 1 - flag
		temp = []
		for i in range(l):
			item = queue.pop(0)
			if flag == 1:
				temp.append(item.data)
			else:
				res.append(item.data)
			if item.left:
				queue.append(item.left)
			if item.right:
				queue.append(item.right)
		temp.reverse()
		for ele in temp:
			res.append(ele)
	return res


def findSpiral(root):
	if not root:
		return []
	else:
		queue = []
		queue.append(root)
		ans = []
		count = 1
		while queue:
			size = len(queue)
			data = []
			for i in range(size):
				temp = queue.pop(0)
				data.append(temp.data)
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
			count += 1
			if count % 2 == 0:
				data = reversed(data)
				ans.extend(data)
			else:
				ans.extend(data)
		return ans


def findSpiral(root):
	result = []
	if root is None:
		return result
	s1 = [root]
	s2 = []
	while s1 or s2:
		while s1:
			root = s1.pop()
			result.append(root.data)
			if root.right:
				s2.append(root.right)
			if root.left:
				s2.append(root.left)
		while s2:
			root = s2.pop()
			result.append(root.data)
			if root.left:
				s1.append(root.left)
			if root.right:
				s1.append(root.right)
	return result


def findSpiral(root):
	if root == None:
		return []
	res = []
	ans = []
	res.append(root)
	flag = 1
	while len(res):
		n = len(res)
		temp = []
		while n:
			curr = res.pop(0)
			temp.append(curr.data)
			if curr.left != None:
				res.append(curr.left)
			if curr.right != None:
				res.append(curr.right)
			n -= 1
		if flag % 2:
			temp = temp[::-1]
		for i in temp:
			ans.append(i)
		flag += 1
	return ans


def findSpiral(root):
	if root == None:
		return []
	res = []
	level = 0
	q = []
	q.append(root)
	while len(q) > 0:
		n = len(q)
		l = []
		for i in range(n):
			curr = q.pop(0)
			l.append(curr.data)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
		if level % 2 == 0:
			res.extend(l[::-1])
		else:
			res.extend(l)
		level += 1
	return res


def findSpiral(root):
	if not root:
		return []
	res = []
	count = 0
	que = deque([root])
	while que:
		k = len(que)
		ans = []
		for i in range(k):
			curr = que.popleft()
			ans.append(curr.data)
			if curr.left:
				que.append(curr.left)
			if curr.right:
				que.append(curr.right)
		if count == 0:
			for i in ans[::-1]:
				res.append(i)
			count = 1
		else:
			for i in ans:
				res.append(i)
			count = 0
	return res


def findSpiral(root):
	if root == None:
		return []
	flag = 1
	q = [root]
	ans = []
	while q:
		temp = []
		for i in range(len(q)):
			node = q.pop(0)
			temp.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if flag == 0:
			ans = ans + temp
			flag = 1
		elif flag == 1:
			t = temp[::-1]
			ans = ans + t
			flag = 0
	return ans


def findSpiral(root):
	q = []
	res = []
	q.append(root)
	flag = False
	if root is None:
		return res
	while len(q):
		n = len(q)
		temp = [0] * n
		for i in range(n):
			node = q.pop(0)
			ind = i if flag else n - i - 1
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			temp[ind] = node.data
		flag = not flag
		res.extend(temp)
	return res


def findSpiral(root):
	q = []
	res = []
	q.append(root)
	ans = []
	while q:
		l = []
		for i in range(len(q)):
			node = q.pop(0)
			if node:
				l.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if l:
			res.append(l)
	for i in range(0, len(res), 2):
		res[i] = res[i][::-1]
	for i in res:
		for j in i:
			ans.append(j)
	return ans


def findSpiral(root):

	def fsp(root):
		if root == None:
			return []
		a = []
		q = [root]
		f = 1
		while len(q) != 0:
			k = len(q)
			for i in range(k):
				if f == 0:
					a.append(q[i].data)
				else:
					a.append(q[k - i - 1].data)
			if f:
				f = 0
			else:
				f = 1
			for i in range(k):
				n = q.pop(0)
				if n.left != None:
					q.append(n.left)
				if n.right != None:
					q.append(n.right)
		return a
	return fsp(root)


def findSpiral(root):
	result = []
	level = 0
	q = []
	if root is None:
		return result
	q.append(root)
	while q:
		length = len(q)
		temp = []
		for i in range(length):
			node = q.pop(0)
			temp.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if level % 2 == 0:
			for i in range(len(temp) - 1, -1, -1):
				result.append(temp[i])
		else:
			result += temp
		level += 1
	return result


def findSpiral(root):
	if not root:
		return []
	que = [root]
	f = 0
	ans = []
	temp = []
	while len(que) != 0:
		for x in range(len(que)):
			curr = que.pop(0)
			temp.append(curr.data)
			if curr.left is not None:
				que.append(curr.left)
			if curr.right is not None:
				que.append(curr.right)
		f += 1
		if f % 2 != 0:
			temp = temp[::-1]
		ans.append(temp)
		temp = []
	return [item for sublist in ans for item in sublist]


def findSpiral(root):
	if root == None:
		return []
	from collections import deque
	queue = deque()
	queue.append(root)
	data = []
	final = []
	nu = 1
	while queue:
		l = []
		for i in range(len(queue)):
			x = queue.popleft()
			l.append(x.data)
			if x.left:
				queue.append(x.left)
			if x.right:
				queue.append(x.right)
		if nu % 2 == 0:
			for j in l:
				final.append(j)
		else:
			for j in l[::-1]:
				final.append(j)
		nu += 1
	return final


def findSpiral(root):
	if root == None:
		return []
	res = []
	q = deque()
	q.append(root)
	c = 1
	while len(q) > 0:
		l = []
		for i in range(0, len(q)):
			A = q.popleft()
			l.append(A.data)
			if A.left:
				q.append(A.left)
			if A.right:
				q.append(A.right)
		if c % 2 == 0:
			for i in l:
				res.append(i)
		else:
			l = l[::-1]
			for i in l:
				res.append(i)
		c = c + 1
	return res


def findSpiral(root):
	ans = []
	if root == None:
		return ans
	queue = []
	queue.append(root)
	lefttoright = True
	while len(queue) != 0:
		size = len(queue)
		res = [0] * size
		for i in range(size):
			temp = queue.pop(0)
			if lefttoright == True:
				index = size - i - 1
			else:
				index = i
			res[index] = temp.data
			if temp.left != None:
				queue.append(temp.left)
			if temp.right != None:
				queue.append(temp.right)
		lefttoright = not lefttoright
		for i in res:
			ans.append(i)
	return ans


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

def findSpiral(root):
	l = []
	res = fun(root, 0, l)
	k = []
	if len(l) > 0:
		k.extend(l[0])
		for i in range(1, len(l)):
			if i % 2 != 0:
				k.extend(l[i])
			else:
				k.extend(l[i][::-1])
	return k


def findSpiral(root):
	if root == None:
		return []
	l = [root, 'a']
	res = [root.data]
	le = 0
	while True:
		w = l.pop(0)
		while w != 'a':
			if w.left:
				l.append(w.left)
			if w.right:
				l.append(w.right)
			w = l.pop(0)
		if l == []:
			return res
		if le % 2 == 1:
			for i in l[::-1]:
				res.append(i.data)
		else:
			for i in l:
				res.append(i.data)
		l.append('a')
		le += 1


def findSpiral(root):
	ans = list()
	(stack1, stack2) = (list(), list())
	stack1.append(root)
	while stack1 or stack2:
		while stack1:
			top1 = stack1.pop()
			if top1:
				ans.append(top1.data)
				if top1.right:
					stack2.append(top1.right)
				if top1.left:
					stack2.append(top1.left)
		while stack2:
			top2 = stack2.pop()
			if top2:
				ans.append(top2.data)
				if top2.left:
					stack1.append(top2.left)
				if top2.right:
					stack1.append(top2.right)
	return ans


def findSpiral(root):
	ans = []
	if root == None:
		return ans
	dirc = True
	q = []
	q.append(root)
	while q:
		size = len(q)
		tx = [-1] * size
		for i in range(size):
			temp = q.pop(0)
			ind = -1
			if dirc == True:
				ind = i
			else:
				ind = size - i - 1
			tx[ind] = temp.data
			if temp.right:
				q.append(temp.right)
			if temp.left:
				q.append(temp.left)
		for j in range(len(tx)):
			ans.append(tx[j])
		dirc = not dirc
	return ans


def findSpiral(root):
	if not root:
		return []
	q = deque()
	q.append(root)
	q.append('$')
	answer = []
	temp = []
	order = False
	while q:
		e = q.popleft()
		if e == '$':
			if order:
				answer.extend(temp)
			else:
				answer.extend(temp[::-1])
			if q:
				temp = []
				order = not order
				q.append('$')
		else:
			temp.append(e.data)
			if e.left != None:
				q.append(e.left)
			if e.right != None:
				q.append(e.right)
	return answer


def findSpiral(root):
	arr = [root]
	fromleft = True
	res = []
	if root == None:
		return res
	while len(arr):
		size = len(arr)
		l = [-1] * size
		for i in range(size):
			index = size - 1 - i if fromleft else i
			temp = arr.pop(0)
			l[index] = temp.data
			if temp.left != None:
				arr.append(temp.left)
			if temp.right != None:
				arr.append(temp.right)
		res = res + l
		fromleft = not fromleft
	return res


def findSpiral(root):
	if not root:
		return []
	q = [[root, 0]]
	res = []
	temp_list = []
	t1 = t2 = []
	i = 0
	while q:
		t = q.pop(0)
		temp = t[0]
		level = t[1]
		if level % 2 == 0:
			if t1:
				res.append(t1)
			t1 = []
			if temp.left:
				q.append([temp.left, level + 1])
			if temp.right:
				q.append([temp.right, level + 1])
			t2.append(temp.data)
		else:
			if t2:
				res.append(t2)
			t2 = []
			if temp.left:
				q.append([temp.left, level + 1])
			if temp.right:
				q.append([temp.right, level + 1])
			t1.append(temp.data)
	if t1:
		res.append(t1)
	if t2:
		res.append(t2)
	final = []
	for i in range(len(res)):
		if i % 2 == 0:
			for e in res[i][::-1]:
				final.append(e)
		else:
			for e in res[i]:
				final.append(e)
	return final


def findSpiral(root):
	queue = [root]
	check = 0
	res = []
	while queue:
		level = []
		val = []
		for i in queue:
			if i == None:
				continue
			val.append(i.data)
			level.append(i.left)
			level.append(i.right)
		if val:
			if check % 2 == 0:
				val = val[::-1]
				res += val
			else:
				res += val
		queue = level
		check += 1
	return res


def findSpiral(root):
	if not root:
		return []
	(ans, de, check) = ([], deque([None, root]), [])
	while de:
		x = de.pop()
		if not x:
			if de:
				de.appendleft(None)
			ans.append(check)
			check = []
		else:
			check.append(x.data)
			if x.left:
				de.appendleft(x.left)
			if x.right:
				de.appendleft(x.right)
	fans = []
	for i in range(len(ans)):
		if i % 2 == 0:
			fans += reversed(ans[i])
		else:
			fans += ans[i]
	return fans


def findSpiral(root):
	out = {}
	if not root:
		return []
	q = [(root, 1)]
	while len(q):
		(node, level) = q[0]
		q.pop(0)
		if node.left:
			q.append((node.left, level + 1))
		if node.right:
			q.append((node.right, level + 1))
		if level not in out:
			out[level] = []
		if level % 2:
			out[level].insert(0, node.data)
		else:
			out[level].append(node.data)
	i = 1
	final = []
	while 1:
		if i not in out:
			break
		for j in out[i]:
			final.append(j)
		i += 1
	return final


def findSpiral(root):
	if not root:
		return []
	(queue, result, flip) = ([root], [], True)
	while queue:
		lvl = []
		for _ in range(len(queue)):
			node = queue.pop(0)
			lvl.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		if flip:
			result.extend(lvl[::-1])
		else:
			result.extend(lvl)
		flip = not flip
	return result


def findSpiral(root):
	if not root:
		return []
	queue = []
	ans = []
	queue.append(root)
	ans.append(root.data)
	level = 0
	while queue:
		another = []
		while queue:
			node = queue.pop(0)
			if node.left:
				another.append(node.left)
			if node.right:
				another.append(node.right)
		queue = another
		if level % 2 == 1:
			for i in range(len(another) - 1, -1, -1):
				ans.append(another[i].data)
		else:
			for i in another:
				ans.append(i.data)
		level += 1
	return ans


def findSpiral(root):
	if not root:
		return []
	q = []
	result = []
	flag = 1
	q.append(root)
	while q:
		(currLev, nextLev) = ([], [])
		for item in q:
			currLev.append(item.data)
			if item.left:
				nextLev.append(item.left)
			if item.right:
				nextLev.append(item.right)
		if flag % 2 != 0:
			result.append(currLev[::-1])
		else:
			result.append(currLev)
		flag += 1
		q = nextLev
	output = [item for lst in result for item in lst]
	return output


def findSpiral(root):
	q = deque([])
	l = []
	if root == None:
		return l
	q.append(root)
	reverse = False
	while q:
		n = len(q)
		l1 = [1] * n
		for i in range(0, n):
			new = q.popleft()
			if reverse == True:
				index = i
			else:
				index = n - 1 - i
			if new.left:
				q.append(new.left)
			if new.right:
				q.append(new.right)
			l1[index] = new.data
		if reverse == True:
			reverse = False
		else:
			reverse = True
		l = l + l1
	return l


def findSpiral(root):
	(l, z) = ([], [])
	if root == None:
		return l
	l.append(root.data)
	z.append(root)
	c = 0
	while z:
		x = len(z)
		y = []
		for i in range(0, x):
			if z[0].left:
				z.append(z[0].left)
				y.append(z[0].left.data)
			if z[0].right:
				z.append(z[0].right)
				y.append(z[0].right.data)
			z.pop(0)
		if c == 0:
			l.extend(y)
			c = 1
		else:
			l.extend(y[-1::-1])
			c = 0
	return l


from collections import deque

def findSpiral(root):
	q = deque()
	q.append(root)
	ans = []
	flag = True
	while q:
		lis = []
		for i in range(len(q)):
			node = q.popleft()
			if node:
				q.append(node.left)
				q.append(node.right)
				lis.append(node.data)
		if flag:
			ans += lis[::-1]
			flag = False
		else:
			ans += lis
			flag = True
	return ans


def findSpiral(root):
	result = []
	if root == None:
		return result
	level = 0
	queue = [root]
	while len(queue) > 0:
		size = len(queue)
		lst = []
		for i in range(size):
			curr = queue.pop(0)
			lst.append(curr.data)
			if curr.left:
				queue.append(curr.left)
			if curr.right:
				queue.append(curr.right)
		if level % 2 == 0:
			result.extend(lst[::-1])
		else:
			result.extend(lst)
		level += 1
	return result


def findSpiral(root):
	if root is None:
		return []
	(s1, s2, res) = ([], [], [])
	s1.append(root)
	while len(s1) or len(s2):
		while len(s1):
			node = s1[-1]
			s1.pop()
			res.append(node.data)
			if node.right:
				s2.append(node.right)
			if node.left:
				s2.append(node.left)
		while len(s2):
			node = s2[-1]
			s2.pop()
			res.append(node.data)
			if node.left:
				s1.append(node.left)
			if node.right:
				s1.append(node.right)
	return res


def findSpiral(root):
	if root == None:
		return []
	q = [root]
	r = []
	level = 1
	while len(q) > 0:
		l = len(q)
		a = []
		for i in range(l):
			temp = q.pop(0)
			a.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		if level % 2 != 0:
			r.extend(a[::-1])
		else:
			r.extend(a)
		level += 1
	return r


from collections import deque

def findSpiral(root):
	ans = []
	queue = deque()
	if not root:
		return ans
	l_to_r = False
	queue.append(root)
	while queue:
		l = len(queue)
		if l_to_r:
			for i in range(l):
				node = queue.popleft()
				ans.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		else:
			for i in range(l):
				node = queue.pop()
				ans.append(node.data)
				if node.right:
					queue.appendleft(node.right)
				if node.left:
					queue.appendleft(node.left)
		l_to_r = not l_to_r
	return ans


class Node:

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

def findSpiral(root):
	if root is None:
		return []
	hashmap = {}
	q = [root]
	root.h = 0
	max_height = -1
	while q:
		temp = q.pop(0)
		height = temp.h
		max_height = max(max_height, height)
		if height not in hashmap:
			hashmap[height] = [temp.data]
		else:
			hashmap[height].append(temp.data)
		if temp.left is not None:
			temp.left.h = height + 1
			q.append(temp.left)
		if temp.right is not None:
			temp.right.h = height + 1
			q.append(temp.right)
	arr = [root.data]
	flag = True
	for i in range(1, max_height + 1):
		if flag:
			arr += hashmap[i]
		else:
			arr += hashmap[i][::-1]
		flag = not flag
	return arr


def findSpiral(root):
	stack1 = [root]
	stack2 = []
	result = []
	while stack1 or stack2:
		while len(stack1):
			node = stack1.pop()
			if node:
				result.append(node.data)
				if node.right:
					stack2.append(node.right)
				if node.left:
					stack2.append(node.left)
		while len(stack2):
			node = stack2.pop()
			if node:
				result.append(node.data)
				if node.left:
					stack1.append(node.left)
				if node.right:
					stack1.append(node.right)
	return result


def findSpiral(root):
	if not root:
		return []
	res = []
	q = []
	flip = False
	q.append(root)
	while q:
		length = len(q)
		temp = []
		while length > 0:
			node = q.pop(0)
			temp.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			length -= 1
		if flip:
			temp.reverse()
		flip = not flip
		while temp:
			res.append(temp.pop())
	return res