Problem Description

You need to implement a throne inheritance system for a kingdom. The kingdom has a hierarchical family structure starting with the king, followed by his children, grandchildren, and so on. The inheritance order follows a specific rule where the throne passes from a person to their oldest child who hasn't been considered yet, and if all children have been considered (or there are no children), it goes back up to find the next eligible relative.

The inheritance order follows these rules:

• Start with the king
• For any person, their oldest child who hasn't been added to the order comes next
• If a person has no children or all their children are already in the order, go back to their parent and find the parent's next oldest child
• This process continues until all living family members are included

You need to implement a ThroneInheritance class with the following methods:

1. Constructor ThroneInheritance(kingName): Initialize the system with the king's name
2. birth(parentName, childName): Record that parentName had a child named childName
3. death(name): Mark a person as dead (they should be excluded from the inheritance order but their descendants can still inherit)
4. getInheritanceOrder(): Return the current inheritance order as a list, excluding dead people

For example, if we have King → Alice (older) and Bob (younger) → Jack (Alice's son):

• The inheritance order would be: ["king", "Alice", "Jack", "Bob"]
• This follows the pattern: king → king's oldest child (Alice) → Alice's child (Jack) → back to king's next child (Bob)

The solution uses a graph representation where each person's children are stored in a hash table. When generating the inheritance order, it performs a depth-first traversal starting from the king, adding each living person to the result and recursively visiting all their children in order.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The throne inheritance system represents a family tree structure where each person (node) can have multiple children (edges). The relationships between family members form a graph structure.

Is it a tree?

• Yes: The family structure is specifically a tree because:
  • There's one root (the king)
  • Each person has exactly one parent (except the king)
  • There are no cycles (you can't be your own ancestor)
  • It's a hierarchical structure with parent-child relationships

DFS

• Conclusion: Since we have a tree structure, the flowchart directly leads us to use DFS (Depth-First Search).

This makes perfect sense for the throne inheritance problem because:

1. We need to traverse the family tree starting from the king (root)
2. The inheritance order follows a preorder traversal pattern - visit a person first, then recursively visit all their children in order
3. DFS naturally handles the recursive nature of the inheritance rules (process parent → process oldest child → process that child's children → backtrack to process next sibling)
4. The solution implements DFS through the recursive dfs(x) function that visits each node and its children in the correct inheritance order

The DFS approach perfectly captures the throne succession logic where we explore each branch of the family tree completely before moving to the next branch, which aligns with how inheritance naturally flows from parent to children before considering siblings.

Intuition

The key insight is recognizing that the throne inheritance order is essentially a preorder traversal of a family tree. When we think about how succession works in real life - the throne passes from parent to eldest child, then to that child's children before moving to younger siblings - this perfectly matches how we visit nodes in a preorder traversal.

Let's trace through why this makes sense. When determining who comes after person X in the inheritance order:

• If X has children who haven't been considered yet, the throne goes to their oldest unconsidered child
• If X has no children or all children have been considered, we need to backtrack to X's parent and find the parent's next child

This recursive backtracking pattern is exactly what happens naturally in a depth-first search. When we use DFS on a tree:

1. We visit the current node (add the person to inheritance order if they're alive)
2. We recursively visit all children in order (process all descendants)
3. When we finish with all children, we automatically backtrack to the parent

The beauty of this approach is that we don't need to explicitly implement the complex Successor function described in the problem. Instead, a simple DFS traversal automatically gives us the correct inheritance order. We just need to:

• Maintain a graph structure g where each parent maps to their list of children (preserving birth order)
• Keep track of dead people in a set dead
• When generating the inheritance order, do a DFS from the king, adding only living people to our result

The death mechanism is elegantly handled - we don't remove dead people from the tree structure (their children still need to inherit), we just skip them when building the final inheritance list. This way, the tree structure remains intact for traversal, but dead people are filtered out from the result.

Learn more about Tree and Depth-First Search patterns.

Solution Approach

The solution implements a preorder traversal of a multi-branch tree using depth-first search. Let's walk through the implementation details:

Data Structures Used:

1. Hash Table (self.g): A defaultdict(list) that maps each parent's name to a list of their children's names. This represents the family tree structure where each person can have multiple children.
2. Set (self.dead): Stores the names of all dead people for O(1) lookup during traversal.
3. String (self.king): Stores the root of our tree (the king's name).

Implementation of Each Method:

__init__(self, kingName):

• Initializes the king as the root of the family tree
• Creates an empty graph g to store parent-child relationships
• Creates an empty set dead to track deceased family members

birth(parentName, childName):

• Simply appends childName to the list of children for parentName in the graph
• The order of insertion matters as children are stored in birth order (oldest to youngest)
• Time complexity: O(1)

death(name):

• Adds the person's name to the dead set
• Doesn't modify the tree structure - dead people's children can still inherit
• Time complexity: O(1)

getInheritanceOrder():

• Performs a DFS traversal starting from the king
• The inner dfs(x) function:
  • First checks if person x is alive using x not in self.dead
  • If alive, adds them to the answer list
  • Then recursively visits all children of x in order
• The traversal naturally follows preorder: visit node → visit all children left to right
• Returns the complete inheritance order excluding dead people
• Time complexity: O(n) where n is the total number of people in the family tree

The elegance of this solution lies in how the DFS traversal automatically handles the complex inheritance rules. By visiting nodes in preorder and maintaining children in birth order, we get the correct succession order without explicitly implementing the recursive Successor function described in the problem.

Example Walkthrough

Let's walk through a concrete example to understand how the DFS approach naturally produces the correct inheritance order.

Initial Setup:

King has two children: Alice (older) and Bob (younger)
Alice has one child: Carol
Bob has two children: David (older) and Eve (younger)

Family Tree Structure:

        King
       /    \
    Alice    Bob
      |      / \
    Carol  David Eve

Step 1: Building the Graph After all births, our graph g looks like:

• g["King"] = ["Alice", "Bob"] (children in birth order)
• g["Alice"] = ["Carol"]
• g["Bob"] = ["David", "Eve"]

Step 2: DFS Traversal for Inheritance Order

Let's trace through the DFS starting from "King":

1. Visit King: Add "King" to result → ["King"]
   • Check King's children: ["Alice", "Bob"]
2. Visit Alice (King's first child): Add "Alice" → ["King", "Alice"]
   • Check Alice's children: ["Carol"]
3. Visit Carol (Alice's child): Add "Carol" → ["King", "Alice", "Carol"]
   • Carol has no children, backtrack to Alice
   • Alice has no more children, backtrack to King
4. Visit Bob (King's second child): Add "Bob" → ["King", "Alice", "Carol", "Bob"]
   • Check Bob's children: ["David", "Eve"]
5. Visit David (Bob's first child): Add "David" → ["King", "Alice", "Carol", "Bob", "David"]
   • David has no children, backtrack to Bob
6. Visit Eve (Bob's second child): Add "Eve" → ["King", "Alice", "Carol", "Bob", "David", "Eve"]
   • Eve has no children, backtrack to Bob
   • Bob has no more children, backtrack to King
   • King has no more children, traversal complete

Final inheritance order: ["King", "Alice", "Carol", "Bob", "David", "Eve"]

Step 3: Handling Deaths

Now suppose Alice dies. We add "Alice" to the dead set.

Running the same DFS traversal:

1. Visit King → Add "King"
2. Visit Alice → Skip (in dead set), but still traverse her children
3. Visit Carol → Add "Carol"
4. Visit Bob → Add "Bob"
5. Visit David → Add "David"
6. Visit Eve → Add "Eve"

New inheritance order: ["King", "Carol", "Bob", "David", "Eve"]

Notice how Carol (Alice's daughter) still inherits even though Alice is dead. The throne would pass: King → Carol (granddaughter through deceased Alice) → Bob → David → Eve.

This demonstrates how the DFS approach elegantly handles both the succession rules and the death mechanism without complex logic - the tree traversal pattern naturally produces the correct order.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(self, kingName): O(1) - Simply initializes the king name, creates an empty set for dead people, and creates an empty defaultdict for the graph.

• birth(self, parentName, childName): O(1) - Appends a child to the parent's list in the graph dictionary, which is a constant time operation.

• death(self, name): O(1) - Adds a name to the dead set, which is a constant time operation in Python.

• getInheritanceOrder(self): O(n) where n is the total number of people in the inheritance tree. The DFS traversal visits each person exactly once, and for each person, it performs constant time operations (checking if they're in the dead set and appending to the result list if not).

Space Complexity:

• Overall space complexity: O(n) where n is the total number of people in the inheritance system.
  • The graph self.g stores all parent-child relationships: O(n) space for storing all people and their children.
  • The self.dead set stores deceased people: O(d) space where d ≤ n is the number of dead people.
  • During getInheritanceOrder(), the recursion stack can go as deep as the height of the tree, which in the worst case (a linear chain) is O(n).
  • The ans list in getInheritanceOrder() stores at most n people: O(n) space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Dead People in the Tree Structure

Pitfall: A common mistake is to remove dead people from the family tree structure when they die. This would break the inheritance chain for their descendants.

# WRONG approach
def death(self, name: str) -> None:
    # Don't do this - it breaks the tree structure!
    del self.family_tree[name]  
    self.dead_people.add(name)

Why it's wrong: Dead people's children should still be able to inherit. If we remove the dead person from the tree, we lose the connection to their descendants.

Correct Solution: Keep dead people in the tree structure but filter them out during traversal:

def death(self, name: str) -> None:
    # Only mark as dead, don't modify tree structure
    self.dead_people.add(name)

2. Using BFS Instead of DFS for Traversal

Pitfall: Using breadth-first search would give incorrect inheritance order because it processes all nodes at the same level before moving to the next level.

# WRONG - BFS gives incorrect order
def getInheritanceOrder(self) -> List[str]:
    from collections import deque
    queue = deque([self.king])
    result = []
  
    while queue:
        person = queue.popleft()
        if person not in self.dead_people:
            result.append(person)
        queue.extend(self.family_tree[person])
  
    return result  # This gives level-order, not inheritance order!

Example showing the difference:

• Tree: King → Alice, Bob; Alice → Jack
• BFS order: [King, Alice, Bob, Jack] ❌
• DFS order: [King, Alice, Jack, Bob] ✅

Correct Solution: Use DFS (preorder traversal) to ensure we fully explore each branch before moving to siblings.

3. Not Preserving Birth Order of Children

Pitfall: Using a data structure that doesn't preserve insertion order for children, or sorting children alphabetically.

# WRONG - Using a set loses birth order
def __init__(self, kingName: str):
    self.family_tree = defaultdict(set)  # Sets don't preserve order!

# WRONG - Sorting children alphabetically
def getInheritanceOrder(self) -> List[str]:
    def dfs(person):
        if person not in self.dead_people:
            result.append(person)
        # Don't sort! Birth order matters
        for child in sorted(self.family_tree[person]):  
            dfs(child)

Why it matters: The inheritance order depends on birth order (oldest to youngest), not alphabetical order.

Correct Solution: Use a list to maintain insertion order:

self.family_tree = defaultdict(list)  # Lists preserve insertion order

4. Forgetting to Handle People with No Children

Pitfall: Not using defaultdict or not checking if a person exists in the dictionary before accessing their children.

# WRONG - KeyError for people with no children
def getInheritanceOrder(self) -> List[str]:
    def dfs(person):
        if person not in self.dead_people:
            result.append(person)
        # This fails if person has no children!
        for child in self.family_tree[person]:  
            dfs(child)

Correct Solution: Use defaultdict(list) which automatically returns an empty list for missing keys, or check existence:

# Option 1: defaultdict handles it automatically
self.family_tree = defaultdict(list)

# Option 2: Check before accessing
if person in self.family_tree:
    for child in self.family_tree[person]:
        dfs(child)