Consider a binary tree whose nodes have ids from 1 to n where n is number of nodes in the tree. The tree is given as a collection of n pairs, where every pair represents node id and sum of children ids.

**Examples:**

Input : 1 5 2 0 3 0 4 0 5 5 6 5 Output: 6 Explanation: In this case, two trees can be made as follows and 6 is the root node. 6 6 / 5 1 4 / 1 4 5 / / 2 3 2 3 Input : 4 0 Output: 4 Explanation: Clearly 4 does not have any children and is the only node i.e., the root node.

At first sight this question appears to be a typical question of tree data structure but it

can be solved as follows.

Every node id appears in children sum except root. So if we do sum of all ids and subtract it from sum of all children sums, we get root.

## C++

`// Find root of tree where children ` `// sum for every node id is given. ` `#include<bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `int` `findRoot(pair<` `int` `, ` `int` `> arr[], ` `int` `n) ` `{ ` ` ` `// Every node appears once as an id, and ` ` ` `// every node except for the root appears ` ` ` `// once in a sum. So if we subtract all ` ` ` `// the sums from all the ids, we're left ` ` ` `// with the root id. ` ` ` `int` `root = 0; ` ` ` `for` `(` `int` `i=0; i<n; i++) ` ` ` `root += (arr[i].first - arr[i].second); ` ` ` ` ` `return` `root; ` `} ` ` ` `// Driver code ` `int` `main() ` `{ ` ` ` `pair<` `int` `, ` `int` `> arr[] = {{1, 5}, {2, 0}, ` ` ` `{3, 0}, {4, 0}, {5, 5}, {6, 5}}; ` ` ` `int` `n = ` `sizeof` `(arr)/` `sizeof` `(arr[0]); ` ` ` `printf` `(` ```
"%d
"
``` `, findRoot(arr, n)); ` ` ` `return` `0; ` `} ` |

## Python3

“””Find root of tree where children

sum for every node id is given”””

def findRoot(arr, n) :

# Every node appears once as an id, and

# every node except for the root appears

# once in a sum. So if we subtract all

# the sums from all the ids, we’re left

# with the root id.

root = 0

for i in range(n):

root += (arr[i][0] – arr[i][1])

return root

# Driver Code

if __name__ == ‘__main__’:

arr = [[1, 5], [2, 0],

[3, 0], [4, 0],

[5, 5], [6, 5]]

n = len(arr)

print(findRoot(arr, n))

# This code is contributed

# by SHUBHAMSINGH10

**Output:**

6

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments