Given a complete binary tree, reverse the nodes present at alternate levels.
Example 1:
Input:
             1
          /   \
        3      2
Output:
             1
          /   \
        2      3
Explanation: Nodes at level 2 are reversed.
Example 2:
Input:
              1
          /      \
         2        3
       /  \      /  \
     42   51   63   72
Output:
             1
          /      \
         3        2
       /  \      /  \
     42   51   63   72
Explanation:
Nodes at level 2 are reversed.
Level 1 and 3 remain as it is.
Your Task:  
You dont need to read input or print anything. Complete the function reverseAlternate() which takes root node as input parameter and modifies the given tree in-place.
Note: If you click on Compile and Test the output will be the in-order traversal of the modified tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
 
Constraints:
1 ≤ N ≤ 10^4

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

'''

def reverseAlternate(root):

    '''

    :param root: root of given tree.

    '''

    # code here

Solutions:
def reverseAlternate(root):
	q = [root]
	lev = 0
	while q:
		l = len(q)
		tmp = []
		for i in range(l):
			p = q[i]
			if lev % 2 == 0:
				if p.left:
					tmp.append(p.left.data)
				if p.right:
					tmp.append(p.right.data)
		tmp = tmp[::-1]
		a = 0
		for i in range(l):
			p = q.pop(0)
			if lev % 2 == 0:
				if p.left and p.right:
					(p.left.data, p.right.data) = (tmp[a], tmp[a + 1])
					a += 2
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
		lev += 1


from collections import deque

def reverseAlternate(root):
	dQ = deque()
	dQ.append(root)
	level = 1
	while dQ:
		level += 1
		times = len(dQ)
		for i in range(times):
			holdnode = dQ.popleft()
			if holdnode.left != None:
				dQ.append(holdnode.left)
			if holdnode.right != None:
				dQ.append(holdnode.right)
		if dQ and level % 2 == 0:
			length = len(dQ)
			for i in range(length // 2):
				(x, y) = (i, length - i - 1)
				(dQ[x].data, dQ[y].data) = (dQ[y].data, dQ[x].data)
	return root


def preorder(root1, root2, lvl):
	if root1 == None or root2 == None:
		return
	if lvl % 2 == 0:
		t = root1.data
		root1.data = root2.data
		root2.data = t
	preorder(root1.left, root2.right, lvl + 1)
	preorder(root1.right, root2.left, lvl + 1)

def reverseAlternate(root):
	preorder(root.left, root.right, 0)


def reverseAlternate(root):
	store = []
	stack = [(root, 0)]
	while stack:
		(head, level) = stack.pop()
		if len(store) == level:
			store.append([])
		if level % 2:
			store[level].append(head.data)
		if head.left:
			stack.append((head.left, level + 1))
			stack.append((head.right, level + 1))
	stack = [(root, 0)]
	while stack:
		(head, level) = stack.pop()
		if head == None:
			break
		if level % 2:
			head.data = store[level].pop()
		if head.left:
			stack.append((head.left, level + 1))
			stack.append((head.right, level + 1))
	return


def reverseAlternate(root):
	if root == None:
		return
	return helper(root.left, root.right, 0)

def helper(root1, root2, level):
	if root1 is None or root2 is None:
		return
	if level % 2 == 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	helper(root1.left, root2.right, level + 1)
	helper(root1.right, root2.left, level + 1)


def reverseAlternate(root):
	level = 1
	q = [root]
	while len(q) != 0:
		temp1 = []
		temp2 = []
		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 == 0:
				temp1.append(node)
				temp2.append(node.data)
		level += 1
		for i in range(len(temp1)):
			temp1[i].data = temp2[len(temp1) - 1 - i]


def reverseAlternate(root):

	def dfs(n1, n2, level):
		if not n1:
			return
		if level % 2:
			(n1.data, n2.data) = (n2.data, n1.data)
		dfs(n1.left, n2.right, level + 1)
		dfs(n1.right, n2.left, level + 1)
	dfs(root.left, root.right, 1)
	return root


def help(left, right, level):
	if left is None or right is None:
		return
	if level % 2 == 0:
		(left.data, right.data) = (right.data, left.data)
	help(left.left, right.right, level + 1)
	help(left.right, right.left, level + 1)

def reverseAlternate(root):
	return help(root.left, root.right, 0)


def reverseAlternate(root):
	dfsRev(root.right, root.left)

def dfsRev(n1, n2, index=True):
	if n1 and n2:
		if index:
			temp = n1.data
			n1.data = n2.data
			n2.data = temp
		dfsRev(n1.left, n2.right, not index)
		dfsRev(n1.right, n2.left, not index)


def reverseAlternate(root):
	if root is None:
		return
	reverseAlternateUtil(root.left, root.right, 0)

def reverseAlternateUtil(node1, node2, level):
	if node1 is None and node2 is None:
		return
	if level % 2 == 0:
		temp = node1.data
		node1.data = node2.data
		node2.data = temp
	reverseAlternateUtil(node1.left, node2.right, level + 1)
	reverseAlternateUtil(node1.right, node2.left, level + 1)


def reverseAlternate(root):

	def helper(root1, root2, index):
		if root1 == None or root2 == None:
			return
		if index % 2 == 0:
			(root1.data, root2.data) = (root2.data, root1.data)
		helper(root1.left, root2.right, index + 1)
		helper(root2.left, root1.right, index + 1)
	return helper(root.left, root.right, 0)


def reverseAlternate(root):
	queue = []
	queue.append(root)
	counter = 1
	ls = []
	while queue:
		count = len(queue)
		for i in range(count):
			curr = queue.pop(0)
			ls.append(curr)
			if curr.left:
				queue.append(curr.left)
			if curr.right:
				queue.append(curr.right)
		if counter % 2 == 0:
			start = 0
			end = len(ls) - 1
			while start < end:
				temp = ls[start].data
				ls[start].data = ls[end].data
				ls[end].data = temp
				start += 1
				end -= 1
		ls = []
		counter += 1


class Queue:

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

	def __str__(self):
		values = []
		values = [str(x) for x in self.l]
		return ' '.join(values)

	def isEmpty(self):
		if self.l == []:
			return True
		else:
			return False

	def Enqueue(self, val):
		self.l.append(val)
		return 'Insertion is completed'

	def Dequeue(self):
		if self.isEmpty():
			return 'Queue is empty'
		else:
			return self.l.pop(0)

def leveltrav(Node, l):
	if not Node:
		return
	else:
		customQueue = Queue()
		customQueue.Enqueue(Node)
		while not customQueue.isEmpty():
			root = customQueue.Dequeue()
			a = l.pop(0)
			root.data = a
			if root.left is not None:
				customQueue.Enqueue(root.left)
			if root.right is not None:
				customQueue.Enqueue(root.right)

def reverseAlternate(root):
	d = {}
	level = 0
	helper(root, level, d)
	l = []
	for i in d:
		if i % 2 != 0:
			d[i] = d[i][::-1]
	for i in d:
		for j in d[i]:
			l.append(j)
	d = {}
	leveltrav(root, l)
	return root

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


def reverseAlternate(root):

	def traverse(root1, root2, level):
		if root1 == None:
			return
		if level % 2 == 0:
			(root1.data, root2.data) = (root2.data, root1.data)
		traverse(root1.left, root2.right, level + 1)
		traverse(root1.right, root2.left, level + 1)
	traverse(root.left, root.right, 2)
	return root


def reverseAlternate(root):

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

	def traversal(root, level):
		if root == None:
			return None
		if level == 0:
			arr.append(root.data)
		else:
			traversal(root.left, level - 1)
			traversal(root.right, level - 1)

	def traversal2(root, level):
		nonlocal count
		if root == None:
			return None
		if level == 0:
			root.data = arr[count]
			count += 1
		else:
			traversal2(root.left, level - 1)
			traversal2(root.right, level - 1)
	arr = []
	for i in range(1, tall, 2):
		traversal(root, i)
		arr = arr[::-1]
		count = 0
		traversal2(root, i)
		arr = []
	return root


def reverseAlternate(root):

	def dfs(r1, r2, level):
		if r1 is None or r2 is None:
			return
		if level:
			(r1.data, r2.data) = (r2.data, r1.data)
		dfs(r1.left, r2.right, not level)
		dfs(r1.right, r2.left, not level)
	dfs(root.left, root.right, True)
	return root


from collections import deque

def reverseAlternate(root):
	if not root:
		return []
	q = deque([root])
	final = []
	level = 0
	while q:
		if level % 2:
			(l, r) = (0, len(q) - 1)
			while l < r:
				(q[l].data, q[r].data) = (q[r].data, q[l].data)
				l += 1
				r -= 1
		for _ in range(len(q)):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		level += 1
	return root


def reverseAlternate(root):
	q = [root]
	level = 0
	while len(q):
		if level % 2 != 0:
			l = 0
			r = len(q) - 1
			while l < r:
				(q[l].data, q[r].data) = (q[r].data, q[l].data)
				l += 1
				r -= 1
		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)
		level += 1
	return root


def preorder(root1, root2, lvl):
	if not root1 or not root2:
		return
	if lvl:
		temp = root1.data
		root1.data = root2.data
		root2.data = temp
	preorder(root1.left, root2.right, not lvl)
	preorder(root1.right, root2.left, not lvl)

def reverseAlternate(root):
	preorder(root.left, root.right, True)
	return root


def reverseAlternate(root):

	def helper(root, root1, k):
		if root and root1:
			if k & 1 == 0:
				l = root.data
				r = root1.data
				root.data = r
				root1.data = l
			helper(root.left, root1.right, k + 1)
			helper(root.right, root1.left, k + 1)
	helper(root.left, root.right, 0)


def reverseAlternate(root):
	q = deque()
	q.append(root)
	level = -1
	while q:
		size = len(q)
		level += 1
		parent = []
		arr = []
		while size:
			ele = q.popleft()
			parent.append(ele)
			if ele.left:
				arr.append(ele.left)
				q.append(ele.left)
			if ele.right:
				arr.append(ele.right)
				q.append(ele.right)
			size -= 1
		if level % 2 == 0 and len(arr) != 0:
			arr.reverse()
			for i in range(len(parent)):
				parent[i].left = arr[2 * i]
				parent[i].right = arr[2 * i + 1]
		elif len(arr) != 0:
			parent.reverse()
			for i in range(len(parent)):
				parent[i].left = arr[2 * i]
				parent[i].right = arr[2 * i + 1]


from collections import deque

def reverseAlternate(root):
	(q, reverse) = (deque([root]), False)
	while q:
		q_copy = deque()
		for _ in range(len(q)):
			node = q.popleft()
			if reverse:
				q_copy.append(node)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if reverse:
			while q_copy:
				(left, right) = (q_copy.popleft(), q_copy.pop())
				(left.data, right.data) = (right.data, left.data)
		reverse = not reverse
	return root


def reverseAlternate(root):
	q = [(root, 0)]
	mapp = {}
	c = 0
	while c != len(q):
		nd = q[c][0]
		lvl = q[c][1]
		if lvl in mapp:
			mapp[lvl].append(nd)
		else:
			mapp[lvl] = [nd]
		if nd.left:
			q.append((nd.left, lvl + 1))
		if nd.right:
			q.append((nd.right, lvl + 1))
		c += 1
	for i in mapp:
		if i % 2 == 0:
			continue
		else:
			k = len(mapp[i]) - 1
			j = 0
			while j < k:
				(mapp[i][j].data, mapp[i][k].data) = (mapp[i][k].data, mapp[i][j].data)
				j += 1
				k -= 1


def reverseAlternate(root):
	c = 0
	q = [[root, 0]]
	m = {}
	while c != len(q):
		t = q[c][0]
		g = q[c][1]
		if g in m:
			m[g].append(t)
		else:
			m[g] = [t]
		if t.left:
			q.append([t.left, g + 1])
		if t.right:
			q.append([t.right, g + 1])
		c += 1
	for i in m:
		if i % 2 == 0:
			continue
		k = len(m[i]) - 1
		j = 0
		while j < k:
			(m[i][j].data, m[i][k].data) = (m[i][k].data, m[i][j].data)
			j += 1
			k -= 1


def reverseAlternate(root):
	q = [root]
	arr = []
	brr = []
	crr = []
	flag = 0
	while q:
		brr = q[0:]
		q = []
		for i in range(len(brr)):
			a = brr[i]
			b = brr[len(brr) - i - 1]
			if flag == 0:
				crr.append(a.data)
			else:
				crr.append(b.data)
			if a.left:
				q.append(a.left)
			if a.right:
				q.append(a.right)
		brr = []
		arr += crr
		crr = []
		if flag == 0:
			flag = 1
		else:
			flag = 0
	q = [root]
	i = 0
	while q:
		t = q.pop(0)
		t.data = arr[i]
		if t.left:
			q.append(t.left)
		if t.right:
			q.append(t.right)
		i += 1
	return root


def reverseAlternate(root):
	if not root:
		return None

	def helper(node1, node2, count):
		if not node1 or not node2:
			return
		if count % 2 != 0:
			(node1.data, node2.data) = (node2.data, node1.data)
		helper(node1.left, node2.right, count + 1)
		helper(node1.right, node2.left, count + 1)
	helper(root.left, root.right, 1)
	return root


def reverseAlternate(root):

	def solve(lroot, rroot, l):
		if lroot == None or rroot == None:
			return
		if l % 2 == 0:
			t = lroot.data
			lroot.data = rroot.data
			rroot.data = t
		solve(lroot.left, rroot.right, l + 1)
		solve(lroot.right, rroot.left, l + 1)
	solve(root.left, root.right, 0)
	return root


from collections import deque

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


def reverseAlternate(root):

	def reverse(rootleft, rootright, level):
		if rootleft == None and rootright == None:
			return
		if level % 2 == 0:
			(rootleft.data, rootright.data) = (rootright.data, rootleft.data)
		reverse(rootleft.left, rootright.right, level + 1)
		reverse(rootleft.right, rootright.left, level + 1)
	reverse(root.left, root.right, 0)
	return root


def reverseAlternate(head):
	if head is None:
		return head
	q = [head]
	if head.left is None:
		return head
	while len(q) > 0:
		j = len(q) - 1
		i = 0
		while i <= j:
			if i == j:
				(q[i].left.data, q[i].right.data) = (q[i].right.data, q[i].left.data)
				break
			else:
				(q[i].left.data, q[j].right.data) = (q[j].right.data, q[i].left.data)
				(q[i].right.data, q[j].left.data) = (q[j].left.data, q[i].right.data)
				i += 1
				j -= 1
		for _ in range(len(q)):
			s = q.pop(0)
			if s.left.left:
				if s.left.left.left:
					q.append(s.left.left)
					q.append(s.left.right)
					q.append(s.right.left)
					q.append(s.right.right)
	return head


from collections import *

def reverseAlternate(root):
	queue = deque()
	reverse = False
	queue.append(root)
	while queue:
		if reverse:
			(i, j) = (0, len(queue) - 1)
			while i < j:
				(queue[i].data, queue[j].data) = (queue[j].data, queue[i].data)
				i += 1
				j -= 1
		reverse = not reverse
		for i in range(len(queue)):
			t = queue.popleft()
			if t.left:
				queue.append(t.left)
			if t.right:
				queue.append(t.right)
	return root


def reverseAlternate(root):
	pass

def reverseAlternate(root):
	if not root:
		return
	solve(root.left, root.right, 2)

def solve(root1, root2, level):
	if not root1 or not root2:
		return
	if level % 2 == 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	solve(root1.left, root2.right, level + 1)
	solve(root1.right, root2.left, level + 1)


def reverseAlternate(root):

	def reverse(root1, root2, level):
		if root1 == None or root2 == None:
			return
		if level % 2 == 0:
			temp = root1.data
			root1.data = root2.data
			root2.data = temp
		reverse(root1.left, root2.right, level + 1)
		reverse(root1.right, root2.left, level + 1)
	reverse(root.left, root.right, 0)


def reverseAlternate(root):

	def reverse(root1, root2, level):
		if root1 == None or root2 == None:
			return
		if level % 2 == 0:
			temp = root1.data
			root1.data = root2.data
			root2.data = temp
		reverse(root1.left, root2.right, level + 1)
		reverse(root1.right, root2.left, level + 1)
	reverse(root.left, root.right, 0)
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

def inorder(root):
	if not root:
		return
	inorder(root.left)
	print(root.data, end=' ')
	inorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		reverseAlternate(root)
		inorder(root)
		print()


def reverse_alternate_level(node):
	queue = list()
	level = 0
	queue.append(node)
	while len(queue) > 0:
		l = len(queue)
		level += 1
		for i in range(0, l):
			temp_node = queue.pop(0)
			if temp_node.left != None:
				queue.append(temp_node.left)
			if temp_node.right != None:
				queue.append(temp_node.right)
		if level % 2 != 0:
			i = 0
			j = len(queue) - 1
			while i < j:
				(queue[i].data, queue[j].data) = (queue[j].data, queue[i].data)
				i += 1
				j -= 1

def reverseAlternate(root):
	reverse_alternate_level(root)
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

def inorder(root):
	if not root:
		return
	inorder(root.left)
	print(root.data, end=' ')
	inorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		reverseAlternate(root)
		inorder(root)
		print()


def reverseAlternate(root):
	zz = zigzag(root)
	(zi, level) = (0, 1)
	que = deque([root])
	while que:
		n = len(que)
		for _ in range(n):
			curr = que.popleft()
			if level % 2 == 0:
				curr.data = zz[zi]
			zi += 1
			if curr.left:
				que.append(curr.left)
			if curr.right:
				que.append(curr.right)
		level += 1

def zigzag(root):
	level = 1
	ans = []
	que = deque([root])
	while que:
		n = len(que)
		curr_level = []
		for _ in range(n):
			curr = que.popleft()
			curr_level.append(curr.data)
			if curr.left:
				que.append(curr.left)
			if curr.right:
				que.append(curr.right)
		if level % 2 == 0:
			curr_level.reverse()
		ans += curr_level
		level += 1
	return ans
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

def inorder(root):
	if not root:
		return
	inorder(root.left)
	print(root.data, end=' ')
	inorder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		reverseAlternate(root)
		inorder(root)
		print()


from collections import deque

def reverseAlternate(root):
	if root == None:
		return root
	if root.left == None and root.right == None:
		return root
	revAlternateUtil(root.left, root.right, 0)
	return root

def revAlternateUtil(root1, root2, level):
	if root1 == None or root2 == None:
		return
	if level % 2 == 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	revAlternateUtil(root1.left, root2.right, level + 1)
	revAlternateUtil(root1.right, root2.left, level + 1)


def swap(root1, root2, level):
	if not root1 or not root2:
		return
	if level % 2 == 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	swap(root1.left, root2.right, level + 1)
	swap(root1.right, root2.left, level + 1)

def reverseAlternate(root):
	if root == None:
		return
	swap(root.left, root.right, 2)


def reverseHepler(root_left, root_right, lvl):
	if root_left == None and root_right == None:
		return
	if lvl % 2 == 0:
		(root_left.data, root_right.data) = (root_right.data, root_left.data)
	reverseHepler(root_left.left, root_right.right, lvl + 1)
	reverseHepler(root_left.right, root_right.left, lvl + 1)

def reverseAlternate(root):
	reverseHepler(root.left, root.right, 0)


def reverseAlternate(root):
	right = []
	rev = []
	if root == None:
		return
	right.append(root)
	while len(right) or len(rev):
		while len(right):
			node = right[0]
			if node.left:
				rev.append(node.left)
			if node.right:
				rev.append(node.right)
			right.pop(0)
		i = 0
		while i < len(rev):
			node = rev[i]
			if node.left:
				right.append(node.left)
			if node.right:
				right.append(node.right)
			i += 1
		n = len(rev)
		for i in range(0, int(len(rev) / 2)):
			temp = rev[i].data
			rev[i].data = rev[n - i - 1].data
			rev[n - i - 1].data = temp
		rev.clear()


def fun(root1, root2, level):
	if root1 == None or root2 == None:
		return
	if level % 2 != 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	fun(root1.left, root2.right, level + 1)
	fun(root1.right, root2.left, level + 1)

def reverseAlternate(root):
	level = 1
	fun(root.left, root.right, level)
	return root


def reverseAlternate(root):
	q = [root]
	l = 0
	while q:
		size = len(q)
		for i in range(size):
			temp = q.pop(0)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		l += 1
		if l % 2 == 1:
			i = 0
			j = len(q) - 1
			while i < j:
				(q[i].data, q[j].data) = (q[j].data, q[i].data)
				i += 1
				j -= 1
	return root


def reverseAlternate(root):
	q = []
	q.append(root)
	q.append('#')
	flag = 0
	reverse_helper = []
	while q:
		node = q.pop(0)
		if node == '#' and q:
			q.append('#')
			flag += 1
		if node != '#' and node.left:
			q.append(node.left)
			if flag % 2 == 0:
				reverse_helper.insert(0, node.left.data)
		if node != '#' and node.right:
			q.append(node.right)
			if flag % 2 == 0:
				reverse_helper.insert(0, node.right.data)
		if flag % 2 == 1 and node != '#':
			node.data = reverse_helper.pop(0)


def reverseAlternate(root):
	a = [root]
	b = []
	while a or b:
		while a:
			p = a.pop()
			if p.left:
				b.append(p.left)
			if p.right:
				b.append(p.right)
		while b:
			for i in b:
				if i.left:
					a.append(i.left)
				if i.right:
					a.append(i.right)
			i = 0
			j = len(b) - 1
			while i < j:
				temp = b[i].data
				b[i].data = b[j].data
				b[j].data = temp
				i += 1
				j -= 1
			b = []
	return root


def reverseAlternate(root):

	def asd(root, level):
		if root == None:
			return None
		else:
			asd(root.left, level + 1)
			asd(root.right, level + 1)
			if level in ans:
				ans[level].append(root.data)
			if level not in ans:
				ans[level] = [root.data]

	def swaps(root, level):
		if root == None:
			return None
		else:
			swaps(root.left, level + 1)
			swaps(root.right, level + 1)
			if level % 2 == 0 and len(ans[level]) > 0:
				root.data = ans[level][-1]
				ans[level].pop()
	ans = {}
	asd(root, 1)
	swaps(root, 1)


def creater(k):
	l = [i.data for i in k]
	for i in range(len(k)):
		k[-(i + 1)].data = l[i]

def reverseAlternate(root):
	if not root:
		return
	if not root.left and (not root.right):
		return
	(d, q) = ({}, [(root, 0)])
	while q:
		(p, l) = q.pop(0)
		if l % 2 == 1:
			if l not in d:
				d[l] = []
			d[l].append(p)
		if p.left:
			q.append((p.left, l + 1))
		if p.right:
			q.append((p.right, l + 1))
	for i in d.values():
		creater(i)


def reverse_alternate_level(node):
	queue = list()
	level = 0
	queue.append(node)
	while len(queue) > 0:
		l = len(queue)
		level += 1
		for i in range(0, l):
			temp_node = queue.pop(0)
			if temp_node.left != None:
				queue.append(temp_node.left)
			if temp_node.right != None:
				queue.append(temp_node.right)
		if level % 2 != 0:
			i = 0
			j = len(queue) - 1
			while i < j:
				(queue[i].data, queue[j].data) = (queue[j].data, queue[i].data)
				i += 1
				j -= 1

def reverseAlternate(root):
	reverse_alternate_level(root)
	return root


def reverse(node1, node2, flag):
	if node1 is None or node2 is None:
		return
	if flag:
		(node1.data, node2.data) = (node2.data, node1.data)
	reverse(node1.left, node2.right, flag ^ 1)
	reverse(node1.right, node2.left, flag ^ 1)

def reverseAlternate(root):
	if root is None:
		return
	if root.left is None and root.right is None:
		return
	reverse(root.left, root.right, 1)


from collections import deque

def reverseAlternate(root):
	q = deque()
	level = 0
	q.append(root)
	while q:
		if level % 2 != 0:
			temp = []
			for i in q:
				temp.append(i.data)
			temp = temp[::-1]
			for i in range(len(temp)):
				q[i].data = temp[i]
		for i in range(len(q)):
			ele = q.popleft()
			if ele.left:
				q.append(ele.left)
			if ele.right:
				q.append(ele.right)
		level += 1


def reverseAlternate(root):

	def solve(root1, root2, level):
		if not root1 and (not root2):
			return
		if level % 2 == 0:
			(root1.data, root2.data) = (root2.data, root1.data)
		solve(root1.left, root2.right, level + 1)
		solve(root1.right, root2.left, level + 1)
	if not root:
		return
	level = 0
	solve(root.left, root.right, level)


def reverseAlternate(root):
	q = deque()
	q.append(root)
	q.append(None)
	level = 1
	temp = []
	while q:
		node = q.popleft()
		if node == None:
			i = 0
			j = len(temp) - 1
			while i < j:
				tempNode = temp[i].data
				temp[i].data = temp[j].data
				temp[j].data = tempNode
				i += 1
				j = j - 1
			temp = []
			if len(q) > 0:
				q.append(None)
				level += 1
		else:
			if level % 2 == 0:
				temp.append(node)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	return root


def reverseAlternate(root):
	if root == None:
		return root
	if root.left == None and root.right == None:
		return root
	revAlternateUtil(root.left, root.right, 0)
	return root

def revAlternateUtil(root1, root2, level):
	if root1 == None or root2 == None:
		return
	if level % 2 == 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	revAlternateUtil(root1.left, root2.right, level + 1)
	revAlternateUtil(root1.right, root2.left, level + 1)


def reverseAlternate(root):
	if root == None:
		return root
	if root.left == None and root.right == None:
		return root
	level = 0
	reverseAlternateUtil(root.left, root.right, level)
	return root

def reverseAlternateUtil(n1, n2, level):
	if n1 == None or n2 == None:
		return
	if level % 2 == 0:
		(n1.data, n2.data) = (n2.data, n1.data)
	reverseAlternateUtil(n1.left, n2.right, level + 1)
	reverseAlternateUtil(n1.right, n2.left, level + 1)


def reverseAlternate(root):
	arr = []
	queue = []
	queue.append(root)
	while len(queue) > 0:
		node = queue.pop(0)
		arr.append(node)
		if node.left != None:
			queue.append(node.left)
		if node.right != None:
			queue.append(node.right)
	N = len(arr)
	start = 0
	step = 1
	flip = False
	while start < N:
		end = min(start + step, N)
		step *= 2
		if flip:
			arr[start:end] = reversed(arr[start:end])
		flip = not flip
		start = end
	for i in range(len(arr) - 1):
		if 2 * i + 1 < N:
			arr[i].left = arr[2 * i + 1]
		else:
			arr[i].left = None
		if 2 * i + 2 < N:
			arr[i].right = arr[2 * i + 2]
		else:
			arr[i].right = None
	return root

def get_str(arr):
	s = ''
	for n in arr:
		s += str(n.data) + ','
	return s


def newNode(item):
	temp = Node(item)
	return temp

def storeAlternate(root, arr, index, l):
	if root == None:
		return index
	index = storeAlternate(root.left, arr, index, l + 1)
	if l % 2 != 0:
		arr[index] = root.data
		index += 1
	index = storeAlternate(root.right, arr, index, l + 1)
	return index

def modifyTree(root, arr, index, l):
	if root == None:
		return index
	index = modifyTree(root.left, arr, index, l + 1)
	if l % 2 != 0:
		root.data = arr[index]
		index += 1
	index = modifyTree(root.right, arr, index, l + 1)
	return index

def reverse(arr, n):
	l = 0
	r = n - 1
	while l < r:
		(arr[l], arr[r]) = (arr[r], arr[l])
		l += 1
		r -= 1

def reverseAlternate(root):
	arr = [0 for i in range(10000)]
	index = 0
	index = storeAlternate(root, arr, index, 0)
	reverse(arr, index)
	index = 0
	index = modifyTree(root, arr, index, 0)


class Node:

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

def reverseAlternate(root):
	if root == None:
		return None
	if root.left == None and root.right == None:
		return root
	x = root.left.data
	root.left.data = root.right.data
	root.right.data = x
	if root.left.left == None:
		return root
	q = deque()
	q.append(root.left)
	q.append(root.right)
	f = 0
	while q:
		for _ in range(len(q) // 2):
			x = q.popleft()
			y = q.popleft()
			if x.left and y.right:
				q.append(x.left)
				q.append(y.right)
			if x.right and y.left:
				q.append(x.right)
				q.append(y.left)
			if f % 2 and x.left and y.right and x.right and y.left:
				t = x.left.data
				x.left.data = y.right.data
				y.right.data = t
				t = x.right.data
				x.right.data = y.left.data
				y.left.data = t
		f += 1
	return root


def reverseAlternate(root):
	queue = [root]
	f = 1
	while queue:
		t = queue.copy()
		queue.clear()
		Data = []
		for e in t:
			Data.append(e.data)
			if e.left:
				queue.append(e.left)
			if e.right:
				queue.append(e.right)
		if f % 2 == 0:
			Data.reverse()
			i = 0
			for e in t:
				e.data = Data[i]
				i += 1
		f += 1


def soln(root1, root2, count):
	if root1 is None and root2 is None:
		return
	if count % 2 == 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	soln(root1.left, root2.right, count + 1)
	soln(root1.right, root2.left, count + 1)

def reverseAlternate(root):
	if root is None:
		return
	soln(root.left, root.right, 0)
	return root


def helper(first, second, level):
	if not first or not second:
		return
	if level:
		(first.data, second.data) = (second.data, first.data)
	helper(first.left, second.right, not level)
	helper(first.right, second.left, not level)

def reverseAlternate(root):
	if not root:
		return
	helper(root.left, root.right, True)


def reverseAlternate(root):
	chane(root.left, root.right, 0)

def chane(root1, root2, l):
	if root1 == None or root2 == None:
		return
	if l % 2 == 0:
		t = root2.data
		root2.data = root1.data
		root1.data = t
	chane(root1.left, root2.right, l + 1)
	chane(root1.right, root2.left, l + 1)


def swap_even_nodes(left, right, level):
	if not left or not right:
		return
	if level % 2 == 0:
		(left.data, right.data) = (right.data, left.data)
	swap_even_nodes(left.left, right.right, level + 1)
	swap_even_nodes(left.right, right.left, level + 1)

def reverseAlternate(root):
	swap_even_nodes(root.left, root.right, 0)
	return root


def reverseAlternate(root):
	queue = []
	queue.append(root)
	r = 0
	while queue:
		n = len(queue)
		for i in range(n):
			node = queue.pop(0)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		if r == 0:
			data = [x.data for x in queue]
			data = data[::-1]
			i = 0
			for x in queue:
				x.data = data[i]
				i += 1
			r = 1
		else:
			r = 0


from collections import deque

def reverseAlternate(root):
	queue = deque()
	if root and root.left:
		(root.left.data, root.right.data) = (root.right.data, root.left.data)
		queue.append(root.left)
		queue.append(root.right)
	level = 1
	while queue:
		num_nodes = len(queue)
		for i in range(num_nodes // 2):
			node1 = queue.popleft()
			node2 = queue.popleft()
			if level % 2 == 0 and node1.left:
				(node1.left.data, node2.right.data) = (node2.right.data, node1.left.data)
				(node1.right.data, node2.left.data) = (node2.left.data, node1.right.data)
			if node1.left:
				queue.append(node1.left)
				queue.append(node2.right)
				queue.append(node1.right)
				queue.append(node2.left)
		level += 1
	return


def reverseAlternate(root):
	if root == None:
		return None
	curr = [root]
	h = 1
	i = 0
	j = len(curr) - 1
	while curr:
		if curr[0] == None:
			break
		i = 0
		j = len(curr) - 1
		temp = [None] * 2 ** h
		while i < j:
			if h % 2 == 0:
				(curr[i].data, curr[j].data) = (curr[j].data, curr[i].data)
			if curr[i].left:
				temp[2 * i] = curr[i].left
			if curr[i].right:
				temp[2 * i + 1] = curr[i].right
			if curr[j].left:
				temp[2 * j] = curr[j].left
			if curr[j].right:
				temp[2 * j + 1] = curr[j].right
			i += 1
			j -= 1
		if i == j:
			if curr[i].left:
				temp[2 * i] = curr[i].left
			if curr[i].right:
				temp[2 * i + 1] = curr[i].right
		curr = temp[:]
		h += 1
	return root


from collections import defaultdict

def reverseAlternate(root):
	q = [(root, 0)]
	level_wise_nodes = defaultdict(list)
	while q:
		(node, level) = q.pop(0)
		level_wise_nodes[level].append(node)
		if node.left is not None:
			q.append((node.left, level + 1))
		if node.right is not None:
			q.append((node.right, level + 1))
	level_wise_nodes = [level_wise_nodes[l] for l in sorted(level_wise_nodes)]
	for level in range(1, len(level_wise_nodes)):
		last = level_wise_nodes[level - 1]
		if level % 2 == 1:
			level_wise_nodes[level] = level_wise_nodes[level][::-1]
		j = 0
		for (i, node) in enumerate(level_wise_nodes[level]):
			if i % 2 == 1:
				last[j].right = node
				j += 1
			else:
				last[j].left = node
	return root


def cal(root1, root2, lv):
	if root1 == None or root2 == None:
		return
	if lv % 2 == 0:
		(root1.data, root2.data) = (root2.data, root1.data)
	cal(root1.left, root2.right, lv + 1)
	cal(root1.right, root2.left, lv + 1)

def reverseAlternate(root):
	cal(root.left, root.right, 0)


def reverseAlternate(root):

	def swapEven(h, dq):
		length = len(dq)
		idx = length - 1
		(front, back) = (0, idx)
		while front < back:
			(n1, n2) = (dq[front][0], dq[back][0])
			(n1.left, n1.right, n2.left, n2.right) = (n2.left, n2.right, n1.left, n1.right)
			front += 1
			back -= 1

	def swapOdd(prev, h, dq):
		length = len(dq)
		idx = length - 1
		for node in prev:
			node.left = dq[idx][0]
			idx -= 1
			node.right = dq[idx][0]
			idx -= 1
	dq = deque([(root, 1)])
	prev = []
	h = 0
	while dq:
		n = len(dq)
		if h % 2 == 1 and dq:
			swapEven(h, dq)
		for _ in range(n):
			(node, h) = dq.popleft()
			if h % 2 == 1:
				prev.append(node)
			if node.left:
				dq.append((node.left, h + 1))
			if node.right:
				dq.append((node.right, h + 1))
		if h % 2 == 1 and dq:
			swapOdd(prev, h, dq)
		prev = []
	return root


def reverseAlternate(root):
	out = []
	s = [root]
	l = 0
	while s:
		s1 = []
		for i in s:
			if i.left:
				s1.append(i.left)
			if i.right:
				s1.append(i.right)
		v = []
		for i in s:
			v.append(i.data)
		if l % 2 != 0:
			v = v[::-1]
		for i in s:
			i.data = v.pop(0)
		l += 1
		s = s1
	return root