We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Throne Inheritance

Number: 1722

Difficulty: Medium

Paid? No

Companies: Snowflake, Google

Problem Description

Implement a ThroneInheritance class that simulates the inheritance order of a royal family. The order starts with the king and follows a depth-first (preorder) traversal of the family tree, giving priority to older children. The twist is that when a person dies, they are skipped in the inheritance order, although their descendants still remain in the order. The design must support adding new children, marking individuals as dead, and retrieving the current inheritance order (skipping dead individuals).

Key Insights

  • Model the family hierarchy as a tree where nodes represent family members and edges represent parent-child relationships.
  • Use a hash table to map a parent's name to a list of their children, preserving the order of birth.
  • Maintain a set of dead members to quickly check if a person should be included in the inheritance order.
  • The inheritance order can be obtained by performing a depth-first (preorder) traversal of the tree.
  • Operations birth and death are efficient (O(1)), while getInheritanceOrder performs a full tree traversal (O(n)).

Space and Time Complexity

Time Complexity:

  • birth: O(1)
  • death: O(1)
  • getInheritanceOrder: O(n) in the worst-case, where n is the number of family members.

Space Complexity:

  • O(n) to store the tree structure and the set of dead members.

Solution

We use a tree (implemented as a dictionary/hash table) to maintain the relationship between parents and children. For each person, we hold a list of their children in order of birth. A separate set keeps track of dead members (to exclude them during the inheritance order retrieval). The getInheritanceOrder function performs a depth-first traversal (preorder) starting from the king. During the traversal, we add each living member to the result list and recursively traverse their children in order.

Code Solutions

class ThroneInheritance:
    def __init__(self, kingName: str):
        # Initialize with the king and an empty tree and set for dead members
        self.king = kingName
        self.tree = {kingName: []}
        self.dead = set()
    
    def birth(self, parentName: str, childName: str) -> None:
        # Add childName to the list of children for parentName, creating an entry for childName in the tree
        if parentName not in self.tree:
            self.tree[parentName] = []
        self.tree[parentName].append(childName)
        self.tree[childName] = []  # Initialize childName in the tree
    
    def death(self, name: str) -> None:
        # Mark the person as dead
        self.dead.add(name)
    
    def getInheritanceOrder(self) -> list:
        # Helper function for preorder traversal
        def dfs(name):
            # If the person is not dead, add to the order list
            if name not in self.dead:
                order.append(name)
            # Traverse the children in the order they were born
            for child in self.tree.get(name, []):
                dfs(child)
        
        order = []
        dfs(self.king)
        return order

# Example usage:
# t = ThroneInheritance("king")
# t.birth("king", "andy")
# t.birth("king", "bob")
# t.birth("andy", "matthew")
# print(t.getInheritanceOrder())
# t.death("andy")
# print(t.getInheritanceOrder())
← Back to All Questions