Code Implementation

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

    def birth(self, parentName: str, childName: str) -> None:
        if parentName not in self.family:
            self.family[parentName] = []
        self.family[parentName].append(childName)
        self.family[childName] = []

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

    def getInheritanceOrder(self) -> list:
        order = []
        def dfs(name):
            if name not in self.dead:
                order.append(name)
            for child in self.family.get(name, []):
                dfs(child)
        dfs(self.king)
        return order
      

class ThroneInheritance {
    string king;
    unordered_map<string, vector<string>> family;
    unordered_set<string> dead;
public:
    ThroneInheritance(string kingName) {
        king = kingName;
        family[kingName] = {};
    }
    void birth(string parentName, string childName) {
        family[parentName].push_back(childName);
        family[childName] = {};
    }
    void death(string name) {
        dead.insert(name);
    }
    vector<string> getInheritanceOrder() {
        vector<string> order;
        function<void(string)> dfs = [&](string name) {
            if (!dead.count(name)) order.push_back(name);
            for (auto &child : family[name]) dfs(child);
        };
        dfs(king);
        return order;
    }
};
      

class ThroneInheritance {
    private String king;
    private Map<String, List<String>> family;
    private Set<String> dead;

    public ThroneInheritance(String kingName) {
        king = kingName;
        family = new HashMap<>();
        family.put(kingName, new ArrayList<>());
        dead = new HashSet<>();
    }

    public void birth(String parentName, String childName) {
        family.get(parentName).add(childName);
        family.put(childName, new ArrayList<>());
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        dfs(king, order);
        return order;
    }

    private void dfs(String name, List<String> order) {
        if (!dead.contains(name)) order.add(name);
        for (String child : family.get(name)) {
            dfs(child, order);
        }
    }
}
      

var ThroneInheritance = function(kingName) {
    this.king = kingName;
    this.family = {};
    this.family[kingName] = [];
    this.dead = new Set();
};

ThroneInheritance.prototype.birth = function(parentName, childName) {
    if (!this.family[parentName]) this.family[parentName] = [];
    this.family[parentName].push(childName);
    this.family[childName] = [];
};

ThroneInheritance.prototype.death = function(name) {
    this.dead.add(name);
};

ThroneInheritance.prototype.getInheritanceOrder = function() {
    const order = [];
    const dfs = (name) => {
        if (!this.dead.has(name)) order.push(name);
        for (const child of this.family[name] || []) dfs(child);
    };
    dfs(this.king);
    return order;
};
      

Problem Description

The "Throne Inheritance" problem simulates the succession order in a royal family. You are required to design a system that models the inheritance of the throne, supporting the following operations:

• ThroneInheritance(kingName): Initializes the inheritance system with the king as the root of the family tree.
• birth(parentName, childName): Records the birth of a child to the given parent.
• death(name): Records the death of the given person. They should be skipped in the inheritance order, but their children are still considered.
• getInheritanceOrder(): Returns the current inheritance order, which is the order in which people would inherit the throne, skipping the dead.

The inheritance order is determined by a pre-order traversal of the family tree, starting from the king, skipping anyone who is dead, but always considering their children.

Key constraints:

• Names are unique within the family.
• Each person can have multiple children, and their order of birth matters.
• The system must efficiently support a sequence of birth, death, and getInheritanceOrder operations.

Thought Process

To solve this problem, we need to model a dynamic family tree that supports quick updates and queries. The main challenge is to maintain the correct order of inheritance as the family grows and as people die.

A brute-force approach might involve reconstructing the entire inheritance order from scratch on every query, but this would be inefficient as the tree grows. Instead, we want a structure that lets us:

• Quickly add children to parents in the correct birth order.
• Mark people as dead without removing them from the tree (since their descendants still matter).
• Efficiently traverse the family tree to produce the current inheritance order, skipping dead people but preserving the order of birth.

This suggests using a tree structure (with the king as the root), and for each person, maintaining a list of children in birth order. We'll also need a way to quickly check if someone is dead.

Solution Approach

Let's break down the solution step by step:

1. Representing the Family Tree:
   • We use a hash map (dictionary) where each key is a person's name and the value is a list of their children, ordered by birth.
   • This allows for O(1) addition of children and efficient traversal.
2. Marking Deaths:
   • We use a set to store the names of dead people.
   • This makes checking if someone is dead an O(1) operation.
3. Handling Births:
   • When a child is born, we append their name to their parent's list in the family tree.
   • We also initialize an empty list for the child, so they can have children later.
4. Generating the Inheritance Order:
   • We perform a pre-order depth-first traversal starting from the king.
   • For each person, if they're not dead, we add them to the order. Then, we recursively process their children in birth order.
5. Why These Structures?
   • Hash maps allow O(1) access and updates for both the family tree and death records.
   • Lists preserve the order of children as required by the problem.
   • DFS traversal ensures we always process parents before their children, matching the inheritance rules.

Example Walkthrough

Let's walk through an example step by step:

ThroneInheritance("king")
birth("king", "andy")
birth("king", "bob")
birth("king", "catherine")
birth("andy", "matthew")
birth("bob", "alex")
birth("bob", "asha")
death("bob")
getInheritanceOrder()
  

• Start with king as the root.
• Children of king: ["andy", "bob", "catherine"]
• Children of andy: ["matthew"]
• Children of bob: ["alex", "asha"]
• bob is marked as dead.
• Now, getInheritanceOrder() does a pre-order traversal:
• king (alive) → add to order
• andy (alive) → add
• matthew (alive) → add
• bob (dead) → skip, but process children
• alex (alive) → add
• asha (alive) → add
• catherine (alive) → add
• Final order: ["king", "andy", "matthew", "alex", "asha", "catherine"]

Time and Space Complexity

• Brute-force approach:
  • Rebuilding the order from scratch on every query would be O(N), where N is the number of people in the family tree, for each getInheritanceOrder() call. If done inefficiently, it could be worse.
• Optimized approach (current solution):
  • birth and death are O(1) operations.
  • getInheritanceOrder is O(N), since we must visit every living person in the family tree once per call.
  • Space complexity is O(N) for the family tree and death set.
• This is optimal since, in the worst case, we must output every living person's name.

Summary

The Throne Inheritance problem is elegantly solved by modeling the family as a tree using hash maps, recording deaths in a set, and using a pre-order traversal to generate the inheritance order. This approach is both efficient and clear, supporting fast updates and queries while accurately reflecting the rules of succession. The use of standard data structures makes the solution robust and easy to understand, and the pre-order traversal naturally matches the inheritance logic required by the problem.