New update is available. Click here to update.

Last Updated: 22 Mar, 2021

Moderate

```
A move may be from parent to child or from child to parent.
```

```
Given βROOTβ = [2,-1,0,-1,-1]
The tree would look like this :
```

```
The answer would be 1, because the root node will transfer 1 coin to its right child. Thus both nodes have the same number of coins now.
```

```
The first line of input contains an integer βTβ denoting the number of test cases.
In the next T lines, the first line contains each test case contains space-separated integers denoting the nodes of the first binary tree, where -1 indicates that the NULL pointer has been appointed to the previous node.
The input is given in a preorder way, that is, the node then left subtree, and then right subtree as shown in the example.
```

```
For each test case, print a single line containing a single integer denoting the number of coins moved.
The output of each test case will be printed in a separate line.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= N <= 10^5
-10^6 <= DATA <= 10^6
Where βTβ is the number of test cases and βNβ denotes the number of nodes in the binary tree, and βDATAβ represents the value of the node.
Time limit: 1 sec.
```

Approaches

The main idea is to use recursion to traverse the tree in a pre-order way and do the following :

- Go to the left subtree and figure how much do we need or if we have got extra? I'll give that/take it away to/from you via our direct edge and pass it to the right child, and if something remains, I'll take it.
- Go to the right subtree and figure how much do we need or if we have got extra? I'll give that/take it away to/from you via our direct edge and pass it to the right child, and if something remains, I'll take it.
- The answer will be the sum of values(absolute) returned after the asked questions from the left subtree and right subtree.
- But what should the root return to its parent? It will return how much "its subtree" needs/has extra. That will be the signed sum of its Left+Right (question's answer) + same question asked to the current root node.