Find root of the tree where children id sum for every node is given

Software Development
#1

Hello Everyone,

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.

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.

// 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\n" , findRoot(arr, n));

return 0;

}

Output:

6

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. I have tried my best to get this solution and also did tested it before creating an article on this topic. There are more such articles on problem statements in my account. Do check out my account and give a like if you love the content.

Thankyou.