Root of the Problem Solution with Approach – CodeChef

Every binary tree problem on CodeChef eventually asks you to reason about structure from partial information. Here is the twist: you know every node’s ID and the sum of its children’s IDs — but not which node is the root. The insight that cracks it is simple — the root is the only node whose ID never shows up as someone’s child.

Problem Statement

Chef has a binary tree with N nodes. Each node has a unique integer ID. For each node, Chef knows the sum of the IDs of its children (0 if it has no children). Given this information, find all possible nodes that could be the root.

Examples

Input	Output	Explanation
N=1, [(4,0)]	4	Single node is trivially the root
N=6, [(1,5),(2,0),(3,0),(4,0),(5,5),(6,5)]	6	sum(ids)=21, sum(child_sums)=15, root=21-15=6

Key Insight

Tree Example:           Child Sums:
      4                     Node 1: children sum = 2+3 = 5
     /                    Node 2: children sum = 0
    2   6                  Node 3: children sum = 0
   /  /                   Node 4: children sum = 2+6 = 8
  1  3 5  7               ...

The root 4 never appears as a child of any node.

Since every node except the root is a child of exactly one other node, the root is the only node whose ID never appears as a child of any other node. However, since we only know child sums (not individual child IDs), we need a different approach.

The key formula: Every edge in the tree contributes a child’s ID to exactly one node’s child sum. So sum(children_sums) = sum of all non-root IDs. Therefore:

root_id = sum(all_ids) - sum(children_sums)

Approach

• Read T test cases
• For each test case, collect all node IDs and all child sums
• Calculate candidate root ID: sum(ids) - sum(child_sums)
• Check if the candidate exists in the ID list — if yes, it is the root
• Output the root (at most one valid root exists per test case)

Implementation

import sys

def find_root_id(node_data):
    """
    node_data: list of (node_id, children_sum) tuples
    Returns the root ID using: root = sum(ids) - sum(children_sums)
    """
    ids = [d[0] for d in node_data]
    child_sums = [d[1] for d in node_data]

    total_id_sum = sum(ids)
    total_child_sum = sum(child_sums)

    root_candidate = total_id_sum - total_child_sum

    # Root is the candidate that appears in the ID list
    if root_candidate in ids:
        return root_candidate
    return -1  # Should never happen per problem guarantee


def solve():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    outputs = []

    for _ in range(t):
        n = int(data[idx])
        idx += 1
        node_data = []
        for _ in range(n):
            node_id = int(data[idx])
            idx += 1
            child_sum = int(data[idx])
            idx += 1
            node_data.append((node_id, child_sum))

        root = find_root_id(node_data)
        outputs.append(str(root) if root != -1 else "")

    sys.stdout.write('n'.join(outputs))


if __name__ == "__main__":
    solve()

Test Run

# Test cases
test_cases = [
    (1, [(4, 0)]),
    (6, [(1, 5), (2, 0), (3, 0), (4, 0), (5, 5), (6, 5)]),
]

for n, data in test_cases:
    root = find_root_id(data)
    print(f"N={n}, root={root}")

Output

N=1, root=4
N=6, root=6

Time and Space Complexity

• Time Complexity: O(N) per test case — single pass to compute sums and a O(1) lookup
• Space Complexity: O(N) for storing node data as list of tuples

The beauty of this solution is that you do not need to reconstruct the tree or simulate any traversal. A single arithmetic observation — root = sum(all IDs) – sum(all child sums) — captures everything needed.

Practice Problems

• CodeChef Binary Tree Problems
• LeetCode Tree Problems

Related Articles

Want to build stronger foundations for tree problems? Read Binary Tree Data Structure in Python to understand traversal patterns, or Level Order Tree Traversal for BFS-based approaches on the same topic cluster.