1
class Tree {
2
  List<Tree> child;
3
  String name;
4

5
  public Tree(String name, List<Tree> child) {
6
    this.name = name;
7
    this.child = child;
8
  }
9
}
10

11
class ThroneInheritance {
12
  private Set<String> death;
13
  private Tree tree;
14
  private Map<String, Tree> addtoTree;
15

16
  public ThroneInheritance(String kingName) {
17
    death = new HashSet<>();
18
    tree = new Tree(kingName, new ArrayList());
19
    addtoTree = new HashMap();
20
    addtoTree.put(kingName, tree);
21
  }
22

23
  public void birth(String parentName, String childName) {
24
    Tree tmp = addtoTree.get(parentName);
25
    Tree childtree = new Tree(childName, new ArrayList());
26
    tmp.child.add(childtree);
27
    addtoTree.put(childName, childtree);
28
  }
29

30
  public void death(String name) {
31
    death.add(name);
32
  }
33

34
  public List<String> getInheritanceOrder() {
35
    List<String> ans = new ArrayList<>();
36
    preOreder(tree, ans, death);
37
    return ans;
38
  }
39

40
  void preOreder(Tree n, List<String> ans, Set<String> death) {
41
    if (n == null) return;
42
    if (!death.contains(n.name)) ans.add(n.name);
43
    for (Tree name : n.child) {
44
      preOreder(name, ans, death);
45
    }
46
  }
47
}