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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Throne Inheritance

Difficulty: Medium

Problem Description

A kingdom consists of a king, his children, his grandchildren, and so on. The kingdom has a well-defined order of inheritance. Implement the ThroneInheritance class that manages the birth and death of family members, and returns the current order of inheritance excluding dead individuals.

Key Insights

  • The inheritance follows a tree structure, where each person can have multiple children.
  • The order of inheritance is defined recursively, favoring the oldest living child.
  • The death of a person doesn't remove them from the inheritance tree; it simply marks them as dead.
  • Efficiently tracking alive and dead members is crucial due to multiple queries on the order of inheritance.

Space and Time Complexity

Time Complexity:

  • O(1) for birth and death operations, as they involve simple data structure modifications.
  • O(n) for getInheritanceOrder, where n is the number of living members, as we need to traverse the entire tree.

Space Complexity:

  • O(n) for storing the family tree and the dead status of each member.

Solution

To solve this problem, we can use a hash table (dictionary) to store each individual and their respective children, creating a tree structure. We also maintain a set to track the deceased members.

  1. Data Structures:

    • A dictionary to represent the family tree, where each key is a person's name and the value is a list of their children.
    • A set to keep track of the names of deceased individuals.

  2. Algorithm:

    • In the constructor, initialize the king and the data structures.
    • For the birth method, add the child to the parent's list in the tree.
    • For the death method, add the person's name to the set of deceased members.
    • For getInheritanceOrder, perform a depth-first traversal of the tree, skipping any members in the deceased set.

Code Solutions

class ThroneInheritance:
    def __init__(self, kingName: str):
        self.tree = {kingName: []}
        self.dead = set()
        self.king = kingName

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

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

    def getInheritanceOrder(self) -> list:
        order = []
        def dfs(name):
            if name not in self.dead:
                order.append(name)
            for child in self.tree.get(name, []):
                dfs(child)
        dfs(self.king)
        return order
← Back to All Questions