Given a Binary tree, the problem is to find mirror of a given node. The mirror of a node is a node which exist at the mirror position of node in opposite subtree at the root.
Example 1:
Input: 
          1        
        /   \       
       2     3     
      / \   / \    
     4   5 6   7   
and target = 4
Output: 7
Explanation: You can see below that the mirror 
node of 4 is 7.
          1       |       1
        /   \     |     /   \
       2     3    |    3     2
      / \   / \   |   / \   / \
     4   5 6   7  |  7   6 5   4
Example 2:
Input: 
        1
      /   \
     2     3
    / \
   4   5
and target = 4
Output: -1
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMirror() which takes root node of the tree and a integer target as input parameter and returns the value of the mirror node of the given target node. If the mirror node does not exists return -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=n<=10^{4}
1<=data of node<=10^{4}
1<=target<=10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
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 findMirror(self,root, target):
        #code here

Solutions:
class Solution:

	def solve(self, l, r, target):
		if not l or not r:
			return -1
		if l.data == target:
			return r.data
		if r.data == target:
			return l.data
		flag = self.solve(l.left, r.right, target)
		if flag != -1:
			return flag
		return self.solve(l.right, r.left, target)

	def findMirror(self, root, target):
		if root.data == target:
			return target
		return self.solve(root.left, root.right, target)


class Solution:

	def Mirror(self, root1, root2, target, ans):
		if root1 == None and root2 == None:
			return
		if root1 == None or root2 == None:
			return
		if root1.data == target:
			ans[0] = root2.data
			return
		self.Mirror(root1.left, root2.right, target, ans)
		self.Mirror(root1.right, root2.left, target, ans)

	def findMirror(self, root, target):
		ans = [-1]
		self.Mirror(root, root, target, ans)
		return ans[0]


class Solution:

	def findMirror(self, root, target):
		q1 = [root]
		q2 = [root]
		while len(q1) and len(q2):
			n = min(len(q1), len(q2))
			queue1 = []
			queue2 = []
			for i in range(n):
				(node1, node2) = (q1[i], q2[i])
				if node1 is None or node2 is None:
					continue
				if node1.data == target:
					return node2.data
				queue1.append(node1.left)
				queue1.append(node1.right)
				queue2.append(node2.right)
				queue2.append(node2.left)
			q1 = queue1
			q2 = queue2
		return -1


class Solution:

	def solve(self, a, b, target):
		if not a or not b:
			return -1
		self.dic[a.data] = b.data
		self.dic[b.data] = a.data
		self.solve(a.left, b.right, target)
		self.solve(a.right, b.left, target)

	def findMirror(self, root, target):
		self.dic = {}
		self.dic[root.data] = root.data
		self.solve(root.left, root.right, target)
		if target not in self.dic:
			return -1
		return self.dic[target]


class Solution:

	def findMirror(self, root, target):
		path = self.findPath(root, target, [])
		for item in path:
			if item == 'left':
				root = root.right
			else:
				root = root.left
			if root is None:
				return -1
		return root.data

	def findPath(self, root, target, path):
		if root is None:
			return []
		if root.data == target:
			return path
		left = self.findPath(root.left, target, path.copy() + ['left'])
		right = self.findPath(root.right, target, path.copy() + ['right'])
		return left + right


class Solution:

	def recur(self, r1, r2, t):
		global ans
		if not r1 or not r2:
			return
		if r1.data == t:
			if r2:
				ans = r2.data
		if r1.left and r2.right:
			self.recur(r1.left, r2.right, t)
		if r1.right and r2.left:
			self.recur(r1.right, r2.left, t)

	def findMirror(self, root, target):
		global ans
		ans = -1
		self.recur(root, root, target)
		return ans


class Solution:

	def mirrorTree(self, root1, root2):
		if root1 is None:
			return
		if root1.data == target:
			self.mirrorNode = root2.data
		if root1.right:
			root2.left = Node(root1.right.data)
			self.mirrorTree(root1.right, root2.left)
		if root1.left:
			root2.right = Node(root1.left.data)
			self.mirrorTree(root1.left, root2.right)

	def helper(self, root1, root2, target):
		if root1 is None or root2 is None:
			return
		if root1.data == target and root2:
			self.mirrorNode = root2.data
		self.helper(root1.left, root2.left, target)
		self.helper(root1.right, root2.right, target)

	def findMirror(self, root, target):
		if root.data == target:
			return root.data
		root1 = Node(root.data)
		self.mirrorTree(root, root1)
		self.mirrorNode = -1
		self.helper(root, root1, target)
		return self.mirrorNode

class Solution:

	def helper(self, root1, root2, target):
		if root1 is None or root2 is None:
			return
		if root1.data == target and root2:
			self.mirrorNode = root2.data
		self.helper(root1.left, root2.right, target)
		self.helper(root1.right, root2.left, target)

	def findMirror(self, root, target):
		if root.data == target:
			return root.data
		self.mirrorNode = -1
		self.helper(root.left, root.right, target)
		self.helper(root.right, root.left, target)
		return self.mirrorNode


class Solution:

	def findMirror(self, root, target):
		if root and root.data == target:
			return target
		if not root:
			return -1
		global k
		k = -1

		def sol(root1, root2):
			global k
			if root1 and root2:
				if root1.data == target:
					if root2:
						k = root2.data
					else:
						k = -1
				if root2.data == target:
					if root1:
						k = root1.data
					else:
						k = -1
				sol(root1.left, root2.right)
				sol(root1.right, root2.left)
		sol(root.left, root.right)
		if k != -1:
			return k
		else:
			return -1


class Solution:

	def findMirror(self, root, target):
		if not root:
			return -1
		arr = []
		if root.data == target:
			return target
		self.findMirrorUtil(root.left, target, arr, [-1])
		self.findMirrorUtil(root.right, target, arr, [1])
		head = root
		for i in arr:
			if i == -1 and head.right:
				head = head.right
			elif i == 1 and head.left:
				head = head.left
			else:
				return -1
		return head.data

	def findMirrorUtil(self, root, target, arr, temp):
		if not root:
			return
		if root.data == target:
			arr.extend(temp)
			return
		self.findMirrorUtil(root.left, target, arr, temp + [-1])
		self.findMirrorUtil(root.right, target, arr, temp + [1])


class Solution:

	def checkMirror(self, left, right):
		if not left or not right:
			return 0
		if left.data == target:
			return right.data
		if right.data == target:
			return left.data
		else:
			return self.checkMirror(left.left, right.right) + self.checkMirror(left.right, right.left)

	def findMirror(self, root, target):
		if root.data == target:
			return root.data
		ans = self.checkMirror(root.left, root.right)
		if not ans:
			return -1
		return ans


class Solution:

	def findMirror(self, root, target):

		def fp(r, t, p):
			if r.data == t:
				return p
			if r.left:
				np = fp(r.left, t, p + 'l')
				if np:
					return np
			if r.right:
				np = fp(r.right, t, p + 'r')
				if np:
					return np
		p = fp(root, target, '')
		n = root
		for c in p:
			if c == 'r':
				if n.left:
					n = n.left
				else:
					return -1
			elif n.right:
				n = n.right
			else:
				return -1
		return n.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
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		target = int(input())
		ob = Solution()
		res = ob.findMirror(root, target)
		print(res)


class Solution:

	def recur(self, r1, r2, target):
		if not r1 and (not r2):
			return -1
		if not r1 or not r2:
			return -1
		if r1.data == target:
			return r2.data
		if r2.data == target:
			return r1.data
		a = self.recur(r1.left, r2.right, target)
		b = self.recur(r1.right, r2.left, target)
		if a != -1:
			return a
		return b

	def findMirror(self, root, target):
		if not root:
			return -1
		if root.data == target:
			return root.data
		return self.recur(root.left, root.right, target)
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
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		target = int(input())
		ob = Solution()
		res = ob.findMirror(root, target)
		print(res)


class Solution:
	ans = -1

	def findMirror(self, root, target):
		if root.data == target:
			return root.data
		if root is None:
			return -1
		else:
			self.isMirror(root.left, root.right, target)
			return self.ans

	def isMirror(self, left, right, target):
		if left is None or right is None:
			return
		if left.data == target:
			self.ans = right.data
		elif right.data == target:
			self.ans = left.data
		self.isMirror(left.left, right.right, target)
		self.isMirror(left.right, right.left, target)


from collections import defaultdict

class Solution:

	def mirror(self, left, right, target):
		if left == None or right == None:
			return -1
		if left.data == target:
			return right.data
		if right.data == target:
			return left.data
		check = self.mirror(left.left, right.right, target)
		if check != -1:
			return check
		return self.mirror(left.right, right.left, target)

	def findMirror(self, root, target):
		if root.data == target:
			return root.data
		return self.mirror(root.left, root.right, target)


class Solution:

	def findMirror(self, root, target):
		if not root:
			return -1
		if target == root.data:
			return root.data
		self.mirror = -1
		self.helper(root.left, root.right, target)
		return self.mirror

	def helper(self, root1, root2, target):
		if root1 == None and root2 == None:
			return None
		if root1 != None and root2 != None:
			if root1.data == target:
				self.mirror = root2.data
			if root2.data == target:
				self.mirror = root1.data
		if root1 == None:
			if root2.data == target:
				self.mirror = -1
			return
		if root2 == None:
			if root1.data == target:
				self.mirror = -1
			return
		self.helper(root1.left, root2.right, target)
		self.helper(root1.right, root2.left, target)


class Solution:

	def helper(self, root):
		if root == None:
			return
		newRoot = Node(root.data)
		newRoot.left = self.helper(root.right)
		newRoot.right = self.helper(root.left)
		return newRoot

	def check(self, root, newRoot, k):
		if root == None or newRoot == None:
			return -1
		if root.data == k:
			return newRoot.data
		ans = self.check(root.left, newRoot.left, k)
		ans1 = self.check(root.right, newRoot.right, k)
		if ans != -1:
			return ans
		elif ans1 != -1:
			return ans1
		return -1

	def findMirror(self, root, target):
		newRoot = self.helper(root)
		return self.check(root, newRoot, target)


class Solution:

	def asd(self, x, y, target, a):
		if x == None or y == None:
			return
		else:
			if x.data == target:
				a.append(y.data)
			self.asd(x.left, y.right, target, a)
			self.asd(x.right, y.left, target, a)

	def findMirror(self, root, target):
		a = []
		self.asd(root, root, target, a)
		if a == []:
			return -1
		return a[0]


class Solution:

	def findMirror(self, root, target):
		if not root:
			return -1
		if root.data == target:
			return target
		mirror = [None]
		self._findMirror(root.left, root.right, target, mirror)
		return mirror[0] if mirror[0] else -1

	def _findMirror(self, left, right, target, mirror):
		if not left or not right:
			return
		if left.data == target:
			mirror[0] = right.data
			return
		if right.data == target:
			mirror[0] = left.data
			return
		self._findMirror(left.left, right.right, target, mirror)
		self._findMirror(left.right, right.left, target, mirror)


class Solution:

	def findMirror(self, root, target):
		if root is None:
			return None

		def search(root, target, path):
			if root is None:
				return (False, [])
			newPath = path.copy()
			newPath.append(root)
			if root.data == target:
				return (True, newPath)
			(found, p) = search(root.left, target, newPath)
			if found:
				return (True, p)
			(found, p) = search(root.right, target, newPath)
			if found:
				return (True, p)
			return (False, [])
		(found, path) = search(root, target, [])
		if not found:
			return -1
		dummyIter = iter = root
		path.pop(0)
		while path:
			try:
				node = path.pop(0)
				if dummyIter.left == node:
					iter = iter.right
				else:
					iter = iter.left
				dummyIter = node
			except:
				return -1
		if iter:
			return iter.data
		return -1


class Solution:

	def recur(self, r1, r2, target):
		global ans
		if not r1 or not r2:
			return
		if r1.data == target:
			ans = r2.data
			return
		elif r2.data == target:
			ans = r1.data
			return
		self.recur(r1.left, r2.right, target)
		self.recur(r1.right, r2.left, target)

	def findMirror(self, root, target):
		if root.data == target:
			return root.data
		global ans
		ans = None
		self.recur(root.left, root.right, target)
		return ans if ans else -1


class Solution:

	def soln(self, node1, node2, target, m):
		if node1 is None or node2 is None:
			return
		if node1.data == target:
			self.m = node2.data
			return
		if node2.data == target:
			self.m = node1.data
			return
		l = self.soln(node1.left, node2.right, target, self.m)
		if self.m != -1:
			return
		return self.soln(node1.right, node2.left, target, self.m)

	def findMirror(self, root, target):
		if root is None:
			return -1
		if root.data == target:
			return target
		self.m = -1
		self.soln(root.left, root.right, target, self.m)
		return self.m


class Solution:

	def findMirror(self, root, target):

		def trav(root, p, k):
			if root is None:
				return 0
			if root.data == p:
				return 1
			y = trav(root.left, p, k)
			if y == 1:
				k.append(1)
				return 1
			x = trav(root.right, p, k)
			if x == 1:
				k.append(-1)
				return 1
			return 0
		k = []
		trav(root, target, k)
		k.reverse()
		for i in k:
			if i == 1:
				root = root.right
			if i == -1:
				root = root.left
			if root is None:
				return -1
		return root.data


class Solution:

	def findMoves(self, node, target):
		if node.data == target:
			return [0]
		left_moves = right_moves = None
		if node.left:
			left_moves = self.findMoves(node.left, target)
		if node.right:
			right_moves = self.findMoves(node.right, target)
		if left_moves:
			return [-1] + left_moves
		if right_moves:
			return [1] + right_moves
		return None

	def findMirror(self, root, target):
		moves = self.findMoves(root, target)
		node = root
		for m in moves[:-1]:
			if m == -1:
				node = node.right
			else:
				node = node.left
			if not node:
				return -1
		return node.data


class Solution:

	def findMirror(self, root, target):
		if root.data == target:
			return target
		kkkk = self.mirror(root.left, root.right, target)
		if kkkk:
			return kkkk
		return -1

	def mirror(self, a, b, target):
		if a and b:
			if a.data == target:
				return b.data
			if b.data == target:
				return a.data
			kk = self.mirror(a.left, b.right, target)
			if kk:
				return kk
			return self.mirror(a.right, b.left, target)


class Solution:

	def findMirror(self, root, target):
		directions = []
		get_directions(root, target, [], directions)
		return find_node(root, directions[0], 0)

def get_directions(cur, target, path, res):
	if not cur:
		return
	if cur.data == target:
		res.append(''.join(path))
		return
	path.append('L')
	get_directions(cur.left, target, path, res)
	path.pop()
	path.append('R')
	get_directions(cur.right, target, path, res)
	path.pop()

def find_node(cur, directions, i):
	if not cur:
		return -1
	if i == len(directions):
		return cur.data
	if directions[i] == 'R':
		return find_node(cur.left, directions, i + 1)
	else:
		return find_node(cur.right, directions, i + 1)