Given a binary tree of size N, your task is to complete the function pairwiseSwap(), that swap leaf nodes in the given binary tree pairwise starting from from left to right.
Example 1:
Input: 
Output: 7 2 1 4 5 9 3 8 6 10 
Explanation:
The sequence of leaf nodes in original binary tree
from left to right is (4, 7, 8, 9, 10). Now if we 
try to form pairs from this sequence, we will have 
two pairs as (4, 7), (8, 9). The last node (10) is 
unable to form pair with any node and thus left unswapped
 
Example 2:
Input: 
          1
       /     \
      2       3
       \    /    \
        5  6      7
Output: 2 6 1 5 3 7
        1
     /     \
    2       3
     \    /   \
      6  5     7
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function pairwiseSwap() which takes root node of the tree as input parameter. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1<=N<=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 pairwiseSwap(self,root):
        #code here

Solutions:
class Solution:

	def fun(self, root, l):
		if root == None:
			return 0
		le = self.fun(root.left, l)
		re = self.fun(root.right, l)
		if le == 0 and re == 0:
			l.append(root)
			if len(l) % 2 == 0:
				t1 = l[-2].data
				l[-2].data = l[-1].data
				l[-1].data = t1

	def pairwiseSwap(self, root):
		l = []
		self.fun(root, l)


class Solution:

	def leaf(self, root, lis):
		if root == None:
			return
		if root.left == None and root.right == None:
			lis.append(root.data)
		self.leaf(root.left, lis)
		self.leaf(root.right, lis)

	def solve(self, root, lis):
		if root == None:
			return
		if root.left == None and root.right == None:
			root.data = lis.pop(0)
		self.solve(root.left, lis)
		self.solve(root.right, lis)

	def pairwiseSwap(self, root):
		lis = []
		self.leaf(root, lis)
		i = 0
		while i < len(lis) - 1:
			(lis[i], lis[i + 1]) = (lis[i + 1], lis[i])
			i += 2
		self.solve(root, lis)
		return root


class Solution:

	def pairwiseSwap(self, root):
		pair = True
		couple = None

		def dfs(node):
			nonlocal pair, couple
			if not node.left and (not node.right):
				pair = not pair
				if pair:
					(couple.data, node.data) = (node.data, couple.data)
				else:
					couple = node
				return
			if node.left:
				dfs(node.left)
			if node.right:
				dfs(node.right)
		dfs(root)


class Solution:

	def __init__(self):
		self.count = 0
		self.firstPointer = None
		self.secondPointer = None

	def swap(self):
		data = self.firstPointer.data
		self.firstPointer.data = self.secondPointer.data
		self.secondPointer.data = data

	def pairwiseSwap(self, root):
		if root is None:
			return
		elif root.left is None and root.right is None:
			self.secondPointer = root
			self.count += 1
			if not self.count % 2:
				self.swap()
			else:
				self.firstPointer = self.secondPointer
		self.pairwiseSwap(root.left)
		self.pairwiseSwap(root.right)


class Solution:

	def dfs(self, root, level):
		if not root:
			return
		if not root.left and (not root.right):
			self.arr.append(root)
		self.dfs(root.left, level + 1)
		self.dfs(root.right, level + 1)

	def pairwiseSwap(self, root):
		self.arr = []
		self.dfs(root, 1)
		for i in range(0, len(self.arr) - 1, 2):
			(self.arr[i].data, self.arr[i + 1].data) = (self.arr[i + 1].data, self.arr[i].data)


class Solution:

	def pairwiseSwap(self, root):
		if not root:
			return
		if not root.left and (not root.right):
			return root
		l = []
		self.helper(root, l)
		for i in range(0, len(l), 2):
			if i + 1 < len(l):
				temp = l[i].data
				l[i].data = l[i + 1].data
				l[i + 1].data = temp

	def helper(self, root, l):
		if not root:
			return
		if not root.left and (not root.right):
			l.append(root)
		self.helper(root.left, l)
		self.helper(root.right, l)


class Solution:

	def pairwiseSwap(self, root):
		arr = []
		self.leafNodes(root, arr)
		if len(arr) % 2:
			arr.pop()
		while arr:
			node1 = arr.pop()
			node2 = arr.pop()
			(node1.data, node2.data) = (node2.data, node1.data)
		return

	def leafNodes(self, root, arr):
		if not root:
			return
		if not root.left and (not root.right):
			arr.append(root)
		self.leafNodes(root.left, arr)
		self.leafNodes(root.right, arr)
		return


class Solution:

	def pairwiseSwap(self, root):

		def traversal(root):
			if root == None:
				return None
			if root.left:
				traversal(root.left)
			if root.left == None and root.right == None:
				list1.append(root.data)
			if root.right:
				traversal(root.right)
		list1 = []
		traversal(root)
		length = len(list1)
		for i in range(0, length, 2):
			list1[i:i + 2] = list1[i:i + 2][::-1]

		def traversal2(root):
			nonlocal count
			if root == None:
				return None
			if root.left:
				traversal2(root.left)
			if root.left == None and root.right == None:
				root.data = list1[count]
				count += 1
			if root.right:
				traversal2(root.right)
		count = 0
		traversal2(root)
		return root


class Solution:

	def inorder(self, root, arr):
		if root == None:
			return
		if not root.left and (not root.right):
			arr.append(root)
			return root
		root.left = self.inorder(root.left, arr)
		root.right = self.inorder(root.right, arr)
		return root

	def pairwiseSwap(self, root):
		arr = []
		root = self.inorder(root, arr)
		for i in range(len(arr) - 1):
			if i % 2 == 0:
				temp = arr[i].data
				arr[i].data = arr[i + 1].data
				arr[i + 1].data = temp
		return root


class Solution:

	def pairwiseSwap(self, root):
		prev = None

		def inorder(root):
			nonlocal prev
			if root == None:
				return
			inorder(root.left)
			if root.left == None and root.right == None:
				if prev != None:
					(prev.data, root.data) = (root.data, prev.data)
					prev = None
				else:
					prev = root
			inorder(root.right)
		inorder(root)


class Solution:

	def pairwiseSwap(self, root):
		prev = None

		def _pairwiseSwap(root):
			nonlocal prev
			if not root:
				return
			if not root.left and (not root.right):
				if not prev:
					prev = root
				else:
					(prev.data, root.data) = (root.data, prev.data)
					prev = None
			_pairwiseSwap(root.left)
			_pairwiseSwap(root.right)
		_pairwiseSwap(root)


class Solution:

	def ino(self, r, l):
		if r is None:
			return
		self.ino(r.left, l)
		if r.left is None and r.right is None:
			l.append(r)
		self.ino(r.right, l)

	def pairwiseSwap(self, root):
		q = [root]
		c = 0
		l = []
		self.ino(root, l)
		i = 0
		n = len(l)
		while i + 1 < n:
			(l[i].data, l[i + 1].data) = (l[i + 1].data, l[i].data)
			i += 2


def getLeaves(root, l):
	if root == None:
		return
	getLeaves(root.left, l)
	if root.left == None and root.right == None:
		l.append(root)
	getLeaves(root.right, l)

class Solution:

	def pairwiseSwap(self, root):
		leaves = []
		getLeaves(root, leaves)
		for i in range(0, len(leaves), 2):
			if i + 1 < len(leaves):
				(leaves[i].data, leaves[i + 1].data) = (leaves[i + 1].data, leaves[i].data)
from collections import deque

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = 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 inord(root):
	if not root:
		return
	inord(root.left)
	print(root.data, end=' ')
	inord(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		ob.pairwiseSwap(root)
		inord(root)
		print()


class Solution:

	def pairwiseSwap(self, root):
		stack = []
		current = root
		stack.append(current)
		count = 0
		while len(stack):
			p = stack.pop()
			if p.right:
				stack.append(p.right)
			if p.left:
				stack.append(p.left)
			if p.right == None and p.left == None:
				count += 1
				if count == 1:
					store = p
					val = store.data
				else:
					store.data = p.data
					p.data = val
					count = 0


class Solution:

	def pairswap(self, root, node):
		if not root:
			return
		if root and (not root.left) and (not root.right):
			if not node[0]:
				node[0] = True
				node[1] = root
			else:
				(root.data, node[1].data) = (node[1].data, root.data)
				node[:] = [False, None]
			return
		self.pairswap(root.left, node)
		self.pairswap(root.right, node)
		return

	def pairwiseSwap(self, root):
		node = [False, None]
		self.pairswap(root, node)


class Solution:

	def recur(self, root, l1):
		if not root:
			return
		if not root.left and (not root.right):
			if l1[0]:
				temp = l1[0].data
				l1[0].data = root.data
				root.data = temp
				l1[0] = None
			else:
				l1[0] = root
			return
		self.recur(root.left, l1)
		self.recur(root.right, l1)

	def pairwiseSwap(self, root):
		self.recur(root, [None])
		return root


class Solution:

	def pairwiseSwap(self, root):

		def inorder(root):
			if root == None:
				return None
			else:
				inorder(root.left)
				if root.left == None and root.right == None:
					ans.append(root.data)
				inorder(root.right)

		def swaps(root):
			if root == None:
				return None
			else:
				swaps(root.left)
				if root.left == None and root.right == None:
					root.data = ans[0]
					ans.pop(0)
				swaps(root.right)
		ans = []
		inorder(root)
		for i in range(0, len(ans) - 1, 2):
			(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
		swaps(root)


class Solution:

	def helper(self, root, last_leaf):
		if root is None:
			return
		self.helper(root.left, last_leaf)
		self.helper(root.right, last_leaf)
		if root.right is None and root.left is None:
			if last_leaf[0] is None:
				last_leaf[0] = root
			else:
				(root.data, last_leaf[0].data) = (last_leaf[0].data, root.data)
				last_leaf[0] = None
		return

	def pairwiseSwap(self, root):
		last_leaf = [None]
		self.helper(root, last_leaf)