Throne Inheritance

Medium

Asked by:

7 views

Topics:

TreesRecursion

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.

In the beginning, curOrder will be ["king"].
Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].
Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].
Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].
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 10⁵ calls will be made to birth and death.
At most 10 calls will be made to getInheritanceOrder.

Try coding it in LeetCode

Throne Inheritance

Medium

Asked by:

7 views

Topics:

TreesRecursion

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.

In the beginning, curOrder will be ["king"].
Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].
Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].
Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].
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 10⁵ calls will be made to birth and death.
At most 10 calls will be made to getInheritanceOrder.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can a person be born and die in the same turn?
If a person dies, do their descendants still inherit according to the order they were born?
Can a person call the `birth` method on themselves or a deceased person?
Is the name of each person guaranteed to be unique?
What is the expected scale of the operations? I.e., the number of `birth`, `death`, and `getInheritanceOrder` calls.

Brute Force Solution

Approach

With throne inheritance, we want to figure out the order of succession, even when people die. The brute force way is like constantly re-calculating the entire family tree's order every time something changes, without any shortcuts.

Here's how the algorithm would work step-by-step:

Whenever someone is born, dies, or we need to know the order, start from scratch.
Look at the current king or queen.
List their children in the order they were born.
For each child, list their children in order.
Continue this process for all descendants.
If someone is dead, skip listing them and their descendants in the inheritance order, even though they are still on the family tree.
The final list is the order of inheritance.

Code Implementation

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.kingName = kingName
        self.familyTree = {kingName: []}
        self.deadPeople = set()

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

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

    def getInheritanceOrder(self) -> list[str]:
        inheritanceOrder = []
        
        def preOrderTraversal(currentPerson):
            # Only add to order if alive.
            if currentPerson not in self.deadPeople:
                inheritanceOrder.append(currentPerson)

            # Iterate through children to maintain birth order
            for child in self.familyTree[currentPerson]:
                preOrderTraversal(child)

        # Start traversal at the king.
        preOrderTraversal(self.kingName)
        return inheritanceOrder

Big(O) Analysis

Time Complexity

O(n) – The dominant operation in this brute-force approach is traversing the family tree to determine the inheritance order. In the worst-case scenario, we might need to visit every member of the family tree once to generate the inheritance list, especially if nobody has died. The number of family members is represented by 'n'. Therefore, the time complexity is directly proportional to the number of nodes in the tree.

Space Complexity

O(N) – The algorithm performs a depth-first traversal of the family tree. In the worst-case scenario, where the family tree is highly unbalanced (e.g., a single lineage), the recursion stack could grow to a depth proportional to the number of individuals in the family tree, denoted as N. Additionally, the final inheritance list being constructed can also contain up to N elements (alive individuals), requiring O(N) space. Therefore, the auxiliary space complexity is O(N), dominated by the recursion depth and the inheritance list.

Optimal Solution

Approach

The problem involves simulating the order in which people inherit a throne. The key idea is to build and maintain a family tree, updating the order based on births and deaths, then listing the living people in the correct order of inheritance.

Here's how the algorithm would work step-by-step:

Create a data structure to represent the family tree, where each person knows their children.
Implement a function to add a new child to a person in the family tree. This will simply add a new child to the list of that person's children.
Implement a function to mark a person as dead. This will simply set a flag indicating that the person is no longer alive.
Implement a function to get the order of inheritance. This is the trickiest part. Start at the king. List the king if he's alive. Then, recursively traverse the tree, listing each living child in the order they were born before moving on to the next child. This is a pre-order traversal, skipping dead people.
The function to get the inheritance order should return a list of names. Each time a request for inheritance is made, the function starts from the king and traverses the family tree.
When someone is born or dies, the data structure is updated accordingly, but the inheritance order is only calculated when requested.

Code Implementation

class ThroneInheritance:

    def __init__(self, king_name: str):
        self.king_name = king_name
        self.family_tree = {king_name: []}
        self.is_alive = {king_name: True}

    def birth(self, parent_name: str, child_name: str):
        self.family_tree[parent_name].append(child_name)
        self.family_tree[child_name] = []
        self.is_alive[child_name] = True

    def death(self, name: str):
        self.is_alive[name] = False

    def getInheritanceOrder(self):
        inheritance_order = []

        def pre_order_traversal(person_name):
            # Only add to order if the person is alive.
            if self.is_alive[person_name]:
                inheritance_order.append(person_name)

            # Iterate through children in order of birth.
            for child_name in self.family_tree[person_name]:
                pre_order_traversal(child_name)

        # Start traversal from the king.
        pre_order_traversal(self.king_name)

        return inheritance_order

# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

Big(O) Analysis

Time Complexity

O(n) – Adding a child and marking someone as dead both take O(1) time, since they only involve updating a list or a flag. The inheritance order retrieval dominates the complexity. It performs a pre-order depth-first traversal of the family tree. In the worst-case scenario, we traverse the entire family tree where n is the number of people, touching each node once. Thus, the time complexity of getting the inheritance order is O(n).

Space Complexity

O(N) – The primary space complexity comes from storing the family tree. Each person in the family tree needs to store references to their children, and a flag indicating whether they are alive or dead. In the worst-case scenario, the tree could be structured such that each person has a constant number of children, resulting in N nodes, where N is the number of people. Additionally, the getInheritanceOrder function uses recursion which, in the worst case where the tree is very deep, can create a recursion stack up to a depth of N, where N is the number of people in the longest branch. Thus, the auxiliary space required is O(N).

Edge Cases

Case	How to Handle
Attempting to kill a non-existent person	The kill operation should gracefully handle this by either ignoring the request or throwing an exception, documenting the behavior clearly.
Attempting to getInheritanceOrder on an empty kingdom (no king)	Return an empty list as there is no inheritance order to generate.
Killing the king	The king should still be considered dead; the getInheritanceOrder must not include a dead king.
Adding a child to a dead person	The add operation should function normally even if the parent is dead, as this is a valid state of the inheritance tree.
Large number of people in the kingdom, potentially exceeding memory limits	Choose data structures that allow efficient memory utilization and consider using iterative approaches instead of deeply recursive ones to prevent stack overflow.
The same name is used for different people (name collisions)	The problem states unique names; explicitly check for name duplication and throw an IllegalArgumentException if detected, or clearly state the consequences.
Deep inheritance tree causing stack overflow with recursive implementations.	Favor an iterative Depth First Search (DFS) over a recursive DFS to avoid stack overflow errors in extremely deep trees.
Adding a child to someone who is already a child of someone else (creating a cycle).	The problem doesn't mention cycles; adding someone already present should be disallowed; throw IllegalArgumentException or handle gracefully.