Throne Inheritance

This problem asks us to design a class ThroneInheritance to model the inheritance order of a monarchy. We are given the king’s name, and over time, births and deaths will occur, which we need to incorporate to maintain the correct order of inheritance. The order of inheritance follows these rules:

  1. The king is the first member of the order.
  2. If a person has a child, that child is next in line after them.
  3. A person’s children are in the order of their birth.
  4. If a person dies, they are excluded from the order of inheritance, but the order of their descendants doesn’t change.

We can use a combination of a dict and a set to track the family tree and the dead members, respectively. The dict will map from a person’s name to their children’s names, and the set will contain the names of dead people. To get the inheritance order, we perform a depth-first search of the family tree, excluding dead people.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class ThroneInheritance:
    def __init__(self, kingName: str):
        self.king = kingName
        self.tree = {kingName: []}
        self.dead = set()

    def birth(self, parentName: str, childName: str) -> None:
        self.tree[parentName].append(childName)
        self.tree[childName] = []

    def death(self, name: str) -> None:
        self.dead.add(name)

    def getInheritanceOrder(self) -> List[str]:
        order = []
        def dfs(name):
            if name not in self.dead:
                order.append(name)
            for child in self.tree[name]:
                dfs(child)
        dfs(self.king)
        return order

The __init__ method initializes the object, creating the family tree with the king as the root and an empty set of dead people.

The birth method adds a child to a parent’s list of children in the family tree.

The death method marks a person as dead by adding their name to the dead set.

The getInheritanceOrder method performs a depth-first search of the family tree to compute the current inheritance order. The dfs helper function visits a person and their descendants in the order of birth, skipping dead people.