1
# Runtime: 1338 ms (Top 35.29%) | Memory: 68.8 MB (Top 82.35%)
2

3

4
class ThroneInheritance:
5

6
    def __init__(self, kingName: str):
7
        # Taking kingName as root
8
        self.root = kingName
9

10
        # notDead will hold all the people who are alive and their level number
11
        self.alive = {}
12
        self.alive[kingName] = 0
13

14
        # hold edges existing in our graph
15
        self.edges = {self.root: []}
16

17
    def birth(self, parentName: str, childName: str) -> None:
18
        # birth --> new child so update alive
19
        self.alive[childName] = self.alive[parentName] + 1
20

21
        # add parent to child edges in the edges dictionary
22
        if parentName in self.edges:
23
            self.edges[parentName].append(childName)
24
            if childName not in self.edges:
25
                self.edges[childName] = []
26
        else:
27
            if childName not in self.edges:
28
                self.edges[childName] = []
29
            self.edges[parentName] = [childName]
30

31
    def death(self, name: str) -> None:
32
        # removing the dead people from alive map
33
        del self.alive[name]
34

35
    def getInheritanceOrder(self) -> List[str]:
36

37
        hierarchy = []
38

39
        def dfs(cur, parent=-1):
40
            nonlocal hierarchy
41

42
            # current person available in alive then only add in hierarchy
43
            if cur in self.alive:
44
                hierarchy.append(cur)
45

46
            # traverse all the children of current node
47
            for i in self.edges[cur]:
48
                if i != parent:
49
                    dfs(i, cur)
50

51
        dfs(self.root)
52
        return hierarchy