Complete the below function wh | CareerCup
Complete the below function which takes an arraylist and displays the list in the expected output
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
// your code
}
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) { ... }
}
}
Example input:
List<Relation> input = newArrayList();
input.add(new Relation("animal", "mammal"));
input.add(new Relation("animal", "bird"));
input.add(new Relation("lifeform", "animal"));
input.add(new Relation("cat", "lion"));
input.add(new Relation("mammal", "cat"));
input.add(new Relation("animal", "fish"));
TreePrinter.printTree(input);
Expected output:
line 1: lifeform
line 2: animal
line 3: mammal
line 4: cat
line 5: lion
line 6: bird
line 7: fish
Complete the below function which takes an arraylist and displays the list in the expected output
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
// your code
}
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) { ... }
}
}
Example input:
List<Relation> input = newArrayList();
input.add(new Relation("animal", "mammal"));
input.add(new Relation("animal", "bird"));
input.add(new Relation("lifeform", "animal"));
input.add(new Relation("cat", "lion"));
input.add(new Relation("mammal", "cat"));
input.add(new Relation("animal", "fish"));
TreePrinter.printTree(input);
Expected output:
line 1: lifeform
line 2: animal
line 3: mammal
line 4: cat
line 5: lion
line 6: bird
line 7: fish
public void printTree(Iterable<Relation> rs){
//build a tree like below with lifeform as root
//and do a traversal.
//lifeform -- animal
//animal -- mammal -- cat-- lion
//animal -- bird
//animal -- fish
//use this set to keep track of children to find out
//which one is the root node.
Set<String> setOfNotRootElements = new HashSet<String>();
//build a tree using HashMap. You can also build the tree
//put a Map inside a Map, but this seems simpler.
HashMap<String, List<String>> map = new HashMap<String, List<String>>();
for(Relation r: rs){
List<String> children = new ArrayList<String>();
if(map.containsKey(r.parent)){
children = map.get(r.parent);
}
children.add(r.child);
map.put(r.parent, children );
//keeping track of children..
setOfNotRootElements.add(r.child);
}
//find the root
Set<String> diffSet = new HashSet<String>(map.keySet());
diffSet.removeAll(setOfNotRootElements);
String root = diffSet.iterator().next();
//traverse the tree.
printNode(root, map);
//lifeform
//animal
//mammal
//cat
//lion
//bird
//fish
}
public void printNode(String parent, HashMap<String, List<String>> map){
System.out.println(parent);
List<String> children = map.get(parent);
if(children != null){
for(String child: children){
printNode(child, map);
}
}
}