## Throne Inheritance Problem Solution

This problem requires implementing a data structure that maintains the order of inheritance in a kingdom, considering births and deaths. The key is efficiently managing the family tree and generating the inheritance order, skipping dead members.

### 1. Naive (Brute Force) Solution

A simple approach is to maintain the family tree using a dictionary or a similar data structure where each person maps to their children. The `getInheritanceOrder` function would then perform a Depth-First Search (DFS) on the tree, starting from the king, and collect the living members in the order they are visited.

#### Implementation Details:

*   **Data Structure**: Use a dictionary/map to store the tree, where keys are person names, and values are lists of their children.
*   **Birth**: Add the child to the parent's list of children.
*   **Death**: Mark the person as dead using a separate set or a flag in the tree node.
*   **getInheritanceOrder**: Perform DFS, adding only living members to the result.

#### Code (Python):

```python
class ThroneInheritance:
    def __init__(self, kingName: str):
        self.king = kingName
        self.children = {}
        self.dead = set()

    def birth(self, parentName: str, childName: str):
        if parentName not in self.children:
            self.children[parentName] = []
        self.children[parentName].append(childName)

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

    def getInheritanceOrder(self):
        order = []
        self.dfs(self.king, order)
        return order

    def dfs(self, person, order):
        if person not in self.dead:
            order.append(person)
        if person in self.children:
            for child in self.children[person]:
                self.dfs(child, order)

Time and Space Complexity:

• Time Complexity:
  • birth: O(1)
  • death: O(1)
  • getInheritanceOrder: O(N), where N is the number of people in the kingdom.
• Space Complexity: O(N) to store the tree and the dead set.

2. Optimal Solution

The above solution is already quite efficient, but the key is to ensure that the DFS in getInheritanceOrder is as streamlined as possible.

Optimizations:

• Using an ordered list (e.g., Python's list) for children ensures that the order of birth is maintained, simplifying the DFS logic.
• Using a set for dead provides O(1) lookup for dead members.

3. Edge Cases

• King's Death: The problem states the death of a person doesn't affect the successor function, so no special handling is needed.
• No Children: If a person has no children, the DFS simply doesn't recurse further down that branch.
• Parent Doesn't Exist: The problem statement specifies that parentName is guaranteed to be alive for each call to birth, so we don't need to handle cases where the parent doesn't exist.

4. Big O Analysis

• Time Complexity:
  • ThroneInheritance: O(1)
  • birth: O(1)
  • death: O(1)
  • getInheritanceOrder: O(N), where N is the number of people in the kingdom.
• Space Complexity: O(N) to store the tree and the dead set.

5. Summary

The solution maintains a tree structure representing the kingdom's family tree and a set to keep track of dead members. The getInheritanceOrder function performs a DFS to generate the inheritance order, excluding dead members. The time complexity is dominated by the DFS, which is O(N), and the space complexity is O(N) to store the tree and dead set.