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

Last Updated : 29 Jul, 2022

Consider a binary tree whose nodes have ids from 1 to n where n is the number of nodes in the tree. The tree is given as a collection of n pairs, where every pair represents node id and the 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 a tree data structure but it
can be solved as follows.

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

Implementation:

C++

Java

Python3

C#

Javascript

Output

Time Complexity: O(n), Where n is the length of the given array.
Auxiliary Space: O(1), As no extra space is used.

GeeksforGeeks

Improve

Previous Article

Merge Two Binary Trees by doing Node Sum (Recursive and Iterative)

Similar Reads

Minimize changes to convert into Tree with root 1, even left children and odd right children

Given, a binary tree, the task is to convert this tree using minimum number of increment-decrement operations into a tree which satisfies the following conditions: The root node is always 1.Every left child of a node is even.Every right child of a node is odd. Return and print the minimum number of increment-decrement operations required at the end

Minimize sum of node values by filling given empty Tree such that each node is GCD of its children

Given a Binary Tree consisting of N nodes having no values in it and an integer X, that represents the value of the root node, the task is to find the minimum sum of all the nodes value of the given Tree such that the value of each node must be the value of GCDs of its children. Also, no two siblings can have the same value. Examples: Input: Output

Queries to find sum of distance of a given node to every leaf node in a Weighted Tree

Given a Undirected Weighted Tree having N nodes and E edges. Given Q queries, with each query indicating a starting node. The task is to print the sum of the distances from a given starting node S to every leaf node in the Weighted Tree.Examples: Input: N = 5, E = 4, Q = 3 1 (4) / \ (2) / \ 4 2 (5)/ \ (3) / \ 5 3Query 1: S = 1 Query 2: S = 3 Query

Node having maximum sum of immediate children and itself in n-ary tree

Given an N-Ary tree, find and return the node for which sum of data of all children and the node itself is maximum. In the sum, data of node itself and data of its immediate children is to be taken. For example in the given tree, maxSum Node = 4 with maximum sum of 28 The idea is we will maintain a integer variable maxsum which contains the maximum

Convert an arbitrary Binary Tree to a tree that holds Children Sum Property - Set 2

Question: Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (You cannot change the structure of the tree and cannot decrement the value of any node). For example, the below tree doesn’t hold the children's sum property, convert it to a tree that holds the pro

Convert an arbitrary Binary Tree to a tree that holds Children Sum Property

Question: Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (You cannot change the structure of the tree and cannot decrement the value of any node). For example, the below tree doesn't hold the children sum property, convert it to a tree that holds the prope

Queries to calculate sum of the path from root to a given node in given Binary Tree

Given an infinite complete binary tree rooted at node 1, where every ith node has two children, with values 2 * i and 2 * (i + 1). Given another array arr[] consisting of N positive integers, the task for each array element arr[i] is to find the sum of the node values that occur in a path from the root node to the node arr[i]. Examples: Input: arr[

Path from the root node to a given node in an N-ary Tree

Given an integer N and an N-ary Tree of the following form: Every node is numbered sequentially, starting from 1, till the last level, which contains the node N.The nodes at every odd level contains 2 children and nodes at every even level contains 4 children. The task is to print the path from the root node to the node N. Examples: Input: N = 14 O

Number of children of given node in n-ary Tree

Given a node x, find the number of children of x(if it exists) in the given n-ary tree. Example : Input : x = 50 Output : 3 Explanation : 50 has 3 children having values 40, 100 and 20. Approach : Initialize the number of children as 0.For every node in the n-ary tree, check if its value is equal to x or not. If yes, then return the number of child

Second unique smallest value of given Binary Tree whose each node is minimum of its children

Given a full binary tree where each node value is the same as the minimum value between its children, the task is to find the second minimum unique value of the tree. Examples: Input: tree: Output: 5Explanation: All the unique values present in the tree are 2, 5 and 7.The second smallest is 5. Input: tree: Output: -1Explanation: All the numbers pre

Article Tags :

Practice Tags :