Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 28 Oct, 2021

Moderate

```
In this example, The mirror of 2 will be 4, the mirror of 3 will be 9 and the mirror of 7 will be 6 so the final answer is (5 * 5) + (2 * 4) + (3 * 9) + (7 * 6) = 102.
```

```
Every Node has a mirror node in the given tree.
```

```
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains the elements of the binary tree in the level order form separated by a single space.
If any node does not have a left or right child, take -1 in its place. Refer to the example below.
```

```
1
2 3
-1 4 5 -1
-1 -1 -1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = null (-1)
Right child of 2 = 4
Left child of 3 = 5
Right child of 3 = null (-1)
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).
Note: The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 -1 4 5 -1 -1 -1 -1 -1
```

```
For each test case, print a single integer denoting the sum of multiplication of each node with its mirror node.
Output for each test case will be printed in a separate line.
```

```
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
```

```
1 <= T <= 100
1 <= N <= 3000
1 <= nodeVal <= 10000
Where ‘nodeVal’ is the value of the node.
Time Limit: 1sec
```

Let’s look at what a mirror node of any node will be. So let’s say we are at some node in the left subtree and want to find the mirror of the current node, so it will be present in the right subtree but will have opposite parents than the current node, i.e. for example if the current node is at: root -> left -> left -> right then its mirror will be at root -> right -> right -> left. Hence what we can do is call a function and pass the right node as a mirror node if we have selected a left node and vice versa.

The steps are as follows:

- Take an integer ‘answer’ in which we will store the final answer.
- Update the value of ‘answer’ as ‘answer’ + (‘root -> data’ * ‘root -> data’) as the mirror of the root node will be the node itself.
- Now call the function ‘mirrorMultiplicationHelper’ and pass left subtree, right subtree and ‘answer’.
- Return ‘answer’.

- Check if the left and right nodes are not empty.
- Update the value of ‘answer’ as (‘answer’ + ‘left -> data’ * ‘right -> data’) % 1000000007.
- Call the function ‘mirrorMultiplicationHelper’ for the left side of the left subtree and right side of the right subtree.
- Call the function ‘mirrorMultiplicationHelper’ for the right side of the left subtree and the left side of the right subtree.

Similar problems

Ninja and Tree

Ninja

Posted: 5 Feb, 2022

Kth Largest Element in BST

Moderate

Posted: 12 Mar, 2022

Height of Binary Tree

Easy

Posted: 22 Apr, 2022

Height of Binary Tree

Easy

Posted: 22 Apr, 2022

Height of Binary Tree

Easy

Posted: 22 Apr, 2022

Min Heap

Moderate

Posted: 5 May, 2022

Min Heap

Moderate

Posted: 5 May, 2022

Locked Binary Tree

Easy

Posted: 12 May, 2022