Subject: Calculating Total Weight of Subtree --- Category: ,1, --- Question

Can you write a computer code for the following problem:

Given a text file with 3 comma-delimited columns of all integers: 'id', 'parent' and 'weight'. Each line represents a node identified by 'id'. 'parent' refers to 'id' of another node. Print out, for each node, the total weight of a subtree below this node.

Here is the solution in Java:

import java.io.*;
import java.util.*;
public class PrintWeight {
   public static void main(String[] a) {
      Hashtable<String, String> parentMap = new Hashtable<String, String>();
      Hashtable<String, Long> weightMap = new Hashtable<String, Long>();
      try {
         BufferedReader input = new BufferedReader(new FileReader(a[0]));
         String line = null;
         while ( (line = input.readLine()) != null ) {
            String[] cols = line.split(",");
            String id = cols[0].trim();
            String parent = cols[1].trim();
            long weight = Long.parseLong(cols[2]);
            
            Long totalWeight = weightMap.get(id);
            if (totalWeight==null) {
               weightMap.put(id, weight);   
            } else {
               weightMap.put(id, totalWeight.longValue()+weight);
            }
            parentMap.put(id, parent);
            
            weight = weightMap.get(id).longValue();
            while ( parent!=null && parent.length()>0 ) {
               totalWeight = weightMap.get(parent);
               if (totalWeight==null) {
                  weightMap.put(parent, weight);
               } else {
                  weightMap.put(parent, totalWeight.longValue()+weight);
               }
               parent = parentMap.get(parent);
            }
         }
         input.close();
      } catch (Exception e) {
         e.printStackTrace();
      }

      Enumeration<String> nodes = weightMap.keys();
      while(nodes.hasMoreElements()) {
         String id = nodes.nextElement();
         long weight = weightMap.get(id).longValue();
         System.out.println(id+", "+weight);
      }         
   }
}