{x}
blog image

Throne Inheritance

A kingdom consists of a king, his children, his grandchildren, and so on. Every once in a while, someone in the family dies or a child is born.

The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let's define the recursive function Successor(x, curOrder), which given a person x and the inheritance order so far, returns who should be the next person after x in the order of inheritance.

Successor(x, curOrder):
    if x has no children or all of x's children are in curOrder:
        if x is the king return null
        else return Successor(x's parent, curOrder)
    else return x's oldest child who's not in curOrder

For example, assume we have a kingdom that consists of the king, his children Alice and Bob (Alice is older than Bob), and finally Alice's son Jack.

  1. In the beginning, curOrder will be ["king"].
  2. Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].
  3. Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].
  4. Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].
  5. Calling Successor(Bob, curOrder) will return null. Thus the order of inheritance will be ["king", "Alice", "Jack", "Bob"].

Using the above function, we can always obtain a unique order of inheritance.

Implement the ThroneInheritance class:

  • ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.
  • void birth(string parentName, string childName) Indicates that parentName gave birth to childName.
  • void death(string name) Indicates the death of name. The death of the person doesn't affect the Successor function nor the current inheritance order. You can treat it as just marking the person as dead.
  • string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.

 

Example 1:

Input
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
Output
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]

Explanation
ThroneInheritance t= new ThroneInheritance("king"); // order: king
t.birth("king", "andy"); // order: king > andy
t.birth("king", "bob"); // order: king > andy > bob
t.birth("king", "catherine"); // order: king > andy > bob > catherine
t.birth("andy", "matthew"); // order: king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // order: king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]

 

Constraints:

  • 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
  • kingName, parentName, childName, and name consist of lowercase English letters only.
  • All arguments childName and kingName are distinct.
  • All name arguments of death will be passed to either the constructor or as childName to birth first.
  • For each call to birth(parentName, childName), it is guaranteed that parentName is alive.
  • At most 105 calls will be made to birth and death.
  • At most 10 calls will be made to getInheritanceOrder.

Solution Explanation: Throne Inheritance

This problem requires designing a system to manage the inheritance order in a kingdom. The inheritance follows a specific order: the king first, then his children (oldest first), then their children (oldest first), and so on, recursively. The system needs to handle births, deaths, and querying the current inheritance order, excluding deceased individuals.

Data Structures:

The optimal way to represent the kingdom's structure is using a combination of:

  • HashMap (or Dictionary): To store the children of each person. The key is the parent's name, and the value is a list of their children's names (ordered by age).
  • HashSet (or Set): To efficiently track deceased individuals.

Algorithm:

  1. __init__(kingName) (Constructor): Initializes the king's name, an empty set for deceased individuals, and an empty HashMap to store parent-child relationships.

  2. birth(parentName, childName): Adds childName to the list of children for parentName in the HashMap. Children are implicitly ordered by the sequence of birth calls for a given parent.

  3. death(name): Adds name to the HashSet of deceased individuals.

  4. getInheritanceOrder(): This is the core function. It performs a depth-first search (DFS) starting from the king, recursively traversing the kingdom's family tree:

    • Base Case: If the current person is dead, it skips them.
    • Recursive Step: If the person is alive, their name is added to the result list. Then, the function recursively calls itself for each of their children (oldest first).

Time and Space Complexity:

  • birth() and death(): O(1) time complexity. Adding/removing an element to a hashmap or set takes constant time on average.
  • getInheritanceOrder(): O(N) time complexity in the worst case, where N is the total number of people in the kingdom. This is because DFS visits each node at most once.
  • Space Complexity: O(N) to store the HashMap of parent-child relationships and the HashSet of deceased individuals.

Code Implementation (Python):

from collections import defaultdict
 
class ThroneInheritance:
 
    def __init__(self, kingName: str):
        self.king = kingName
        self.dead = set()
        self.children = defaultdict(list)
 
    def birth(self, parentName: str, childName: str) -> None:
        self.children[parentName].append(childName)
 
    def death(self, name: str) -> None:
        self.dead.add(name)
 
    def getInheritanceOrder(self) -> List[str]:
        result = []
        def dfs(name):
            if name not in self.dead:
                result.append(name)
            for child in self.children[name]:
                dfs(child)
        dfs(self.king)
        return result

Other languages (Java, C++, Go, Typescript, C#) follow a very similar structure, using their respective HashMap/Dictionary and HashSet/Set implementations. The core logic of DFS remains the same. Refer to the detailed code provided in the original response for implementations in these languages.