You are given a binary tree. Your task is pretty straightforward. You have to find the sum of the product of each node and its mirror image (The mirror of a node is a node which exists at the mirror position of the node in opposite subtree at the root.). Don’t take into account a pair more than once. The root node is the mirror image of itself.
 
Example 1:
Input:
      4         
    /    \
   5      6
Output:
46
Explanation:
Sum = (4*4) + (5*6) = 46
Example 2:
Input:
                       1                 
                   /        \
                 3            2
                  /  \         /  \
              7     6       5    4
            /   \    \     /  \    \
          11    10    15  9    8    12
Output:
332
Explanation:
Sum = (1*1) + (3*2) + (7*4) + (6*5) + (11*12) + (15*9) = 332
 
Your Task:
You need to complete the function imgMultiply() that takes root as parameter and returns the required sum.The answer may be very large, compute the answer modulo 10^{9} + 7.
Expected Time Complexity: O(Number of nodes).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:            
1 <= Number of nodes <= 10^{5}
1 <= Data of a node <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3
'''
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
'''

class Solution:
    # your task is to complete this function
    def imgMultiply(self, root):
        # Code here

Solutions:
class Solution:

	def solve(self, l, r):
		if not l or not r:
			return None
		self.ans = (self.ans + l.data * r.data) % self.M
		self.solve(l.left, r.right)
		if l != r:
			self.solve(l.right, r.left)

	def imgMultiply(self, root):
		self.ans = 0
		self.M = int(1000000000.0 + 7)
		self.solve(root, root)
		return self.ans


class Solution:

	def solve(self, root1, root2, lis):
		if root1 == None or root2 == None:
			return
		k = root1.data * root2.data
		lis.append(k)
		self.solve(root1.left, root2.right, lis)
		self.solve(root1.right, root2.left, lis)

	def imgMultiply(self, root):
		lis = [root.data * root.data]
		self.solve(root.left, root.right, lis)
		return sum(lis) % 1000000007


class Solution:

	def imgMultiply(self, root):

		def dfs(l, r):
			if l == None:
				return 0
			elif r == None:
				return 0
			return l.data * r.data + dfs(l.left, r.right) + dfs(l.right, r.left)
		return (root.data ** 2 + dfs(root.left, root.right)) % (10 ** 9 + 7)


class Solution:

	def ImageMultiplication(self, root1, root2, sum, mod):
		if root1 == None and root2 == None:
			return
		if root1 == None or root2 == None:
			return
		sum[0] = (sum[0] + root1.data * root2.data) % mod
		if root1.left != None and root2.right != None:
			self.ImageMultiplication(root1.left, root2.right, sum, mod)
		if root1.right != None and root2.left != None:
			self.ImageMultiplication(root1.right, root2.left, sum, mod)

	def imgMultiply(self, root):
		mod = 10 ** 9 + 7
		sum = [root.data * root.data]
		self.ImageMultiplication(root.left, root.right, sum, mod)
		return sum[0] % mod


class Solution:

	def imgMultiply(self, root):
		global s
		s = root.data * root.data

		def sol(root1, root2):
			global s
			if root1 and root2:
				s = s + root1.data * root2.data
				sol(root1.left, root2.right)
				sol(root1.right, root2.left)
		sol(root.left, root.right)
		return s % (10 ** 9 + 7)


class Solution:

	def ino(self, r, h, p, m):
		if r is None:
			return
		m[p] = [h, r.data, 0]
		self.ino(r.left, h + 1, 2 * p, m)
		self.ino(r.right, h + 1, 2 * p + 1, m)

	def imgMultiply(self, root):
		m = {}
		self.ino(root, 0, 1, m)
		s = 0
		for i in m:
			if m[i][2] == 1:
				continue
			k = i - 2 ** m[i][0]
			k1 = 2 ** (m[i][0] + 1) - 1 - k
			if k1 in m:
				s += m[i][1] * m[k1][1] % 1000000007
				m[k1][2] = 1
		return s % 1000000007


class Solution:

	def imgMultiply(self, root):
		(q1, q2) = ([root], [root])
		mod = 10 ** 9 + 7
		prod = 0
		while len(q1) and len(q2):
			(queue1, queue2) = ([], [])
			n = min(len(q1), len(q2))
			for i in range(n):
				(node1, node2) = (q1[i], q2[i])
				if node1 is None or node2 is None:
					continue
				prod = (prod + node1.data * node2.data) % mod
				(node1.data, node2.data) = (0, 0)
				queue1.append(node1.left)
				queue1.append(node1.right)
				queue2.append(node2.right)
				queue2.append(node2.left)
			(q1, q2) = (queue1, queue2)
		return prod


class Solution:

	def imgMultiply(self, root):
		return (root.data ** 2 + self.helper(root.left, root.right)) % (10 ** 9 + 7)

	def helper(self, root, mirror):
		if root is None or mirror is None:
			return 0
		left = self.helper(root.left, mirror.right)
		right = self.helper(root.right, mirror.left)
		return (left + right + root.data * mirror.data) % (10 ** 9 + 7)


class Solution:

	def solve(self, a, b):
		if not a or not b:
			return
		self.res += a.data * b.data
		self.solve(a.left, b.right)
		self.solve(a.right, b.left)

	def imgMultiply(self, root):
		self.res = root.data * root.data
		self.solve(root.left, root.right)
		return self.res % (10 ** 9 + 7)


class Solution:

	def imgMultiply(self, root):
		x = root.data * root.data
		x += self.D(root.left, root.right)
		return x % (10 ** 9 + 7)

	def D(self, l, r):
		if l and r:
			z = l.data * r.data + self.D(l.left, r.right) + self.D(l.right, r.left)
			return z
		else:
			return 0


class Solution:

	def imgMultiply(self, root):

		def traversal(root1, root2):
			nonlocal sum1
			if root1 == None and root2 == None:
				return None
			elif root1 != None and root2 != None:
				if root1.left and root2.right:
					sum1 += root1.left.data * root2.right.data
					traversal(root1.left, root2.right)
				if root1.right and root2.left:
					traversal(root1.right, root2.left)
		sum1 = 0
		traversal(root, root)
		sum1 += root.data ** 2
		return sum1 % (10 ** 9 + 7)


class Solution:

	def helper(self, node1, node2):
		if not node1 or not node2:
			return
		self.res += node1.data * node2.data
		self.helper(node1.left, node2.right)
		self.helper(node1.right, node2.left)

	def imgMultiply(self, root):
		self.res = root.data * root.data
		self.helper(root.left, root.right)
		return self.res % (10 ** 9 + 7)
from collections import deque

class Solution:

	def imgMultiply(self, root):
		res = root.data ** 2
		if root.left and root.right:
			q = deque()
			q.append(root.left)
			q.append(root.right)
			res += root.left.data * root.right.data
			while q:
				node1 = q.popleft()
				node2 = q.popleft()
				if node1.left and node2.right:
					q.append(node1.left)
					q.append(node2.right)
					res += node1.left.data * node2.right.data
				if node1.right and node2.left:
					q.append(node1.right)
					q.append(node2.left)
					res += node1.right.data * node2.left.data
		return res % (10 ** 9 + 7)


class Solution:

	def helper(self, node1, node2):
		if not node1 or not node2:
			return
		self.res += node1.data * node2.data
		self.helper(node1.left, node2.right)
		self.helper(node1.right, node2.left)

	def imgMultiply(self, root):
		self.res = root.data * root.data
		self.helper(root.left, root.right)
		return self.res % (10 ** 9 + 7)


class Solution:

	def imgMultiply(self, root):

		def util(left, right):
			nonlocal count
			if left and right:
				count += left.data * right.data
				util(left.left, right.right)
				util(left.right, right.left)
		count = root.data * root.data
		util(root.left, root.right)
		return count % (pow(10, 9) + 7)


class Solution:

	def helper(self, r1, r2):
		if not r1 or not r2:
			return 0
		return r1.data * r2.data + self.helper(r1.left, r2.right) + self.helper(r1.right, r2.left)

	def imgMultiply(self, root):
		if root:
			return (root.data * root.data + self.helper(root.left, root.right)) % (10 ** 9 + 7)


class Solution:

	def imgMultiply(self, root):
		head = None
		head = self._copy(root, head)
		result = [0]
		self.mul(root.left, head.left, result)
		return (result[0] + root.data * root.data) % (10 ** 9 + 7)

	def _copy(self, root, head):
		if not root:
			return
		head = Node(root.data)
		head.right = self._copy(root.left, head.right)
		head.left = self._copy(root.right, head.left)
		return head

	def mul(self, root, head, result):
		if not head or not root:
			return
		result[0] += head.data * root.data
		self.mul(root.left, head.left, result)
		self.mul(root.right, head.right, result)


class Solution:

	def imgMultiply(self, root):

		def pro(root1, root2):
			nonlocal sum1
			if root1 == None or root2 == None:
				return 0
			sum1 += root1.data * root2.data
			pro(root1.left, root2.right)
			pro(root1.right, root2.left)
		sum1 = 0
		pro(root.left, root.right)
		sum1 += root.data ** 2
		return sum1 % (10 ** 9 + 7)


from collections import deque
import sys
sys.setrecursionlimit(50000)

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

class Solution:

	def imgMultiply(self, root):
		d = {}

		def df(r, p):
			if r.left:
				np = p + '0'
				d[np] = r.left.data
				df(r.left, np)
			if r.right:
				np = p + '1'
				d[np] = r.right.data
				df(r.right, np)
		df(root, '1')
		s = 0
		for k in d:
			l = bin(2 ** (len(k) + 1) - 1 ^ int('1' + k, 2))[2:]
			l = '1' + '0' * (len(k) - 1 - len(l)) + l
			if l in d:
				s += d[k] * d[l]
		return (root.data ** 2 + s // 2) % (10 ** 9 + 7)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		ans = obj.imgMultiply(root)
		print(ans)


from collections import deque
import sys
sys.setrecursionlimit(50000)

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

class Solution:
	mod = 10 ** 9 + 7

	def recur(self, r1, r2):
		if not r1 or not r2:
			return 0
		a = self.recur(r1.left, r2.right)
		b = self.recur(r1.right, r2.left)
		m = r1.data * r2.data % Solution.mod
		return (a + b + m) % Solution.mod

	def imgMultiply(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return root.data * root.data % Solution.mod
		ans = self.recur(root.left, root.right)
		ans = (root.data * root.data % Solution.mod + ans) % Solution.mod
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		ans = obj.imgMultiply(root)
		print(ans)


class Solution:

	def mirror(self, left, right, ans):
		if left == None or right == None:
			return
		self.mirror(left.left, right.right, ans)
		ans[0] += left.data * right.data
		self.mirror(left.right, right.left, ans)

	def imgMultiply(self, root):
		ans = [root.data * root.data]
		self.mirror(root.left, root.right, ans)
		return ans[0] % (10 ** 9 + 7)


class Solution:

	def imgMultiply(self, root):
		if not root:
			return 0
		self.sum = root.data ** 2
		self.helper(root.left, root.right)
		return self.sum % (10 ** 9 + 7)

	def helper(self, root1, root2):
		if root1 == None and root2 == None:
			return
		if root1 != None and root2 != None:
			self.sum += root1.data * root2.data
			self.helper(root1.left, root2.right)
			self.helper(root1.right, root2.left)
		return


import sys
sys.setrecursionlimit(100001)

class Solution:

	def imgMultiply(self, root):
		ans = [root.data * root.data % 1000000007]
		self.helper(root.left, root.right, ans)
		return ans[0] % 1000000007

	def helper(self, node1, node2, ans):
		if node1 is None or node2 is None:
			return
		ans[0] = ans[0] + node1.data * node2.data % 1000000007
		self.helper(node1.left, node2.right, ans)
		self.helper(node1.right, node2.left, ans)


class Solution:

	def __init__(self):
		self.MOD = 10 ** 9 + 7

	def solve(self, r1, r2):
		if r1 == None or r2 == None:
			return 0
		if r1 == r2:
			return (r1.data * r2.data % self.MOD + self.solve(r1.left, r2.right) % self.MOD) % self.MOD
		else:
			return (r1.data * r2.data % self.MOD + self.solve(r1.left, r2.right) % self.MOD + self.solve(r1.right, r2.left) % self.MOD) % self.MOD

	def imgMultiply(self, root):
		return self.solve(root, root)


class Solution:

	def recur(self, r1, r2):
		global ans
		if not r1 or not r2:
			return
		ans = (ans + r1.data * r2.data % (10 ** 9 + 7)) % (10 ** 9 + 7)
		if r1 != r2:
			self.recur(r1.left, r2.right)
			self.recur(r1.right, r2.left)
		else:
			self.recur(r1.left, r2.right)
		return ans

	def imgMultiply(self, root):
		global ans
		ans = 0
		self.recur(root, root)
		return ans


class Solution:

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

	def imgMultiply(self, root):
		a = []
		b = []
		self.asd(root, root, a, b)
		sum = a[0] * b[0]
		for i in range(len(a)):
			sum += a[i] * b[i]
		return sum // 2 % (pow(10, 9) + 7)


class Solution:

	def imgMultiply(self, root):

		def h(root1, root2):
			if root1 is None or root2 is None:
				return 0
			left_sm = h(root1.left, root2.right)
			right_sm = h(root1.right, root2.left)
			pair_sm = root1.data * root2.data
			return left_sm + right_sm + pair_sm
		return (h(root.left, root.right) + root.data * root.data) % 1000000007


class Solution:

	def imgMultiply(self, root):
		if not root:
			return 0
		product = [root.data * root.data]
		self._imgMultiply(root.left, root.right, product)
		return product[0] % (pow(10, 9) + 7)

	def _imgMultiply(self, left, right, product):
		if not left or not right:
			return
		product[0] = product[0] + left.data * right.data
		self._imgMultiply(left.left, right.right, product)
		self._imgMultiply(left.right, right.left, product)


class Solution:

	def imgMultiply(self, root):
		if root is None:
			return None
		self.res = root.data ** 2

		def mult(root, left, right):
			if left and right:
				self.res += left.data * right.data
				mult(root, left.left, right.right)
				mult(root, left.right, right.left)
		mult(root, root.left, root.right)
		return self.res % (10 ** 9 + 7)


class Solution:

	def imgMultiply(self, root):
		mod = 10 ** 9 + 7
		ans = root.data ** 2 % mod

		def util(l, r):
			nonlocal ans
			if l is None or r is None:
				return
			ans = (ans + l.data * r.data % mod) % mod
			util(l.left, r.right)
			util(l.right, r.left)
		util(root.left, root.right)
		return ans


class Solution:

	def __init__(self):
		self.ans = 0
		self.mod = 1000000000.0 + 7

	def multiply(self, node1, node2):
		if node1 is None and node2 is None or ((node1 is not None and node2 is None) and (node1 is None and nod2 is not None)):
			return 0
		else:
			self.ans += int(node1.data % self.mod * node2.data % self.mod % self.mod)
		if node1.left is not None and node2.right is not None:
			self.multiply(node1.left, node2.right)
		if node1.right is not None and node2.left is not None:
			self.multiply(node1.right, node2.left)
		return

	def imgMultiply(self, root):
		if root is None:
			return 0
		else:
			SumR = root.data * root.data
			if root.left is not None and root.right is not None:
				self.multiply(root.left, root.right)
				return int((SumR + self.ans) % self.mod)
			else:
				return int(SumR % self.mod)