Throne Inheritance - Leetcode Solution

Throne Inheritance is a problem on LeetCode. The problem is to design a class that represents a kingdom's family tree and provides methods for adding and removing members, as well as an iterator for traversing the tree in a pre-order traversal.

Solution:

To solve this problem, we need to represent the family tree as a graph. Each node in the graph represents a person, and the edges represent the parent-child relationships.

We can use a HashMap to store the mapping between a person's name and its corresponding node in the graph. We can also store the name of the king in a variable. To traverse the tree in a pre-order traversal, we can use a Stack.

The class will have the following methods:

1. init(kingName: str) - this method will initialize the class with the name of the king and create the HashMap to store the graph.

2. birth(parentName: str, childName: str) - this method will add a child to a parent. We need to check if the parent exists in the graph, if not, we'll create a new node for the parent and add it to the graph. Then we'll create a new node for the child and add it as a child node to the parent. If the parent has not had any children yet, we'll mark the child as 'alive', otherwise, we'll mark it as 'notalive'.

3. death(name: str) - this method will mark a person as dead. We'll set the 'alive' flag to 'false' for the node that represents the person.

4. getInheritanceOrder() - this method will provide an iterator for traversing the graph in pre-order traversal.

To create the iterator, we'll use a Stack. We'll push the king's node onto the Stack and iterate through the Stack while it is not empty. For each node, we'll check if it is 'alive', if so, we'll add it to the inheritance order, and then add its children in reverse order onto the Stack.

The complete code for the Throne Inheritance class is given below:

class Person:
    def __init__(self, name):
        self.name = name
        self.children = []
        self.alive = True
        
class ThroneInheritance:
    
    def __init__(self, kingName: str):
        self.king = Person(kingName)
        self.name_to_person = {kingName: self.king}

    def birth(self, parentName: str, childName: str) -> None:
        parent = self.name_to_person[parentName]
        child = Person(childName)
        parent.children.append(child)
        self.name_to_person[childName] = child

    def death(self, name: str) -> None:
        person = self.name_to_person[name]
        person.alive = False

    def getInheritanceOrder(self) -> List[str]:
        inheritance_order = []
        stack = [self.king]
        while stack:
            node = stack.pop()
            if node.alive:
                inheritance_order.append(node.name)
            for child in reversed(node.children):
                stack.append(child)
        return inheritance_order

Time Complexity:

• The birth method takes O(1) time to add a new node to the graph.
• The death method takes O(1) time to mark a person as dead.
• The getInheritanceOrder method takes O(n) time to traverse the graph in pre-order traversal, where n is the number of nodes in the graph.

Therefore, the overall time complexity of the solution is O(n).

1