#1600

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Throne Inheritance

Throne Inheritance requires modeling a dynamic family tree with births and deaths to determine the kingdom's inheritance order efficiently.

hash table tree depth first search design

Problem Statement

A kingdom maintains a royal family with a king, their children, grandchildren, and so on. At any time, a new child can be born to an existing member, and any member may die. The inheritance order starts with the king and follows a recursive rule: each person's oldest living child comes next, then that child's descendants recursively, before moving to the next sibling.

Implement a system that tracks the inheritance order dynamically. Specifically, support operations to record births, deaths, and retrieve the current inheritance order. For example, if the king has children Alice and Bob, with Alice having a son Jack, the inheritance order should reflect the oldest-to-youngest hierarchy, skipping deceased members when requested.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Successor(x, curOrder): if x has no children or all of x's children are in curOrder: if x is the king return null else return Successor(x's parent, curOrder) else return x's oldest child who's not in curOrder

Example 2

Input: See original problem statement.

Output: See original problem statement.

Input ["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"] [["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]] Output [null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]

Explanation ThroneInheritance t= new ThroneInheritance("king"); // order: king t.birth("king", "andy"); // order: king > andy t.birth("king", "bob"); // order: king > andy > bob t.birth("king", "catherine"); // order: king > andy > bob > catherine t.birth("andy", "matthew"); // order: king > andy > matthew > bob > catherine t.birth("bob", "alex"); // order: king > andy > matthew > bob > alex > catherine t.birth("bob", "asha"); // order: king > andy > matthew > bob > alex > asha > catherine t.getInheritanceOrder(); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"] t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherine t.getInheritanceOrder(); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]

Constraints

1 <= kingName.length, parentName.length, childName.length, name.length <= 15
kingName, parentName, childName, and name consist of lowercase English letters only.
All arguments childName and kingName are distinct.
All name arguments of death will be passed to either the constructor or as childName to birth first.
For each call to birth(parentName, childName), it is guaranteed that parentName is alive.
At most 105 calls will be made to birth and death.
At most 10 calls will be made to getInheritanceOrder.

Solution Approach

Tree Structure with Hash Map

Create a tree where each node represents a family member and stores their children in birth order. Maintain a hash map to quickly access nodes by name for birth and death operations, ensuring O(1) node retrieval.

Depth-First Search Traversal

Compute the inheritance order via DFS starting from the king, recursively visiting children in order. Skip nodes marked as deceased to maintain the correct live inheritance sequence without modifying the tree structure.

Efficient Updates on Birth and Death

On a birth, append the child to the parent's children list. On a death, mark the member as deceased in a set. Both operations avoid full tree traversal, allowing getInheritanceOrder to compute efficiently using DFS and the live-members set.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity for getInheritanceOrder is O(N) where N is the total number of living descendants, as DFS visits each node once. Birth and death operations are O(1) due to hash map access and set marking. Space complexity is O(N) for storing the tree nodes and live/deceased states.

What Interviewers Usually Probe

Clarify whether deaths remove nodes or just mark them.
Expect a tree structure that preserves children order for DFS traversal.
Ask about efficient retrieval after multiple births and deaths without full recomputation.

Common Pitfalls or Variants

Common pitfalls

Forgetting to skip deceased members in DFS leading to incorrect inheritance order.
Modifying the tree structure on death instead of using a marker, which complicates updates.
Assuming unordered children or using BFS, which breaks the oldest-to-youngest traversal requirement.

Follow-up variants

Track inheritance with arbitrary parent-to-child ordering instead of oldest-first priority.
Allow multiple kings or parallel family branches requiring merged DFS traversal.
Implement additional queries like 'who is the nth in line' without traversing the full tree.

FAQ

How does Throne Inheritance relate to tree traversal patterns?

The problem is fundamentally a DFS traversal over a tree where each node is a family member, ensuring the correct inheritance order recursively.

Do I remove nodes when a family member dies?

No, mark them as deceased in a set. This allows DFS to skip them while keeping child order intact.

Can the inheritance order change after multiple births?

Yes, each birth adds a new child to the parent's node. DFS will traverse them in birth order, reflecting changes correctly.

What data structures are optimal for Throne Inheritance?

Use a tree for parent-child relationships and a hash map for fast name-to-node lookups, along with a set to track deceased members.

How do I efficiently retrieve the inheritance order repeatedly?

Use DFS starting from the king, skipping deceased members. This avoids recalculating the entire tree while maintaining order.

terminal

Solution

Solution 1: Preorder Traversal of a Multi-branch Tree

According to the problem description, we can find that the order of throne inheritance is actually a preorder traversal of a multi-branch tree. We can use a hash table $g$ to store the children of each person, and a set $dead$ to store the people who have died.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.dead = set()
        self.g = defaultdict(list)

    def birth(self, parentName: str, childName: str) -> None:
        self.g[parentName].append(childName)

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

    def getInheritanceOrder(self) -> List[str]:
        def dfs(x: str):
            x not in self.dead and ans.append(x)
            for y in self.g[x]:
                dfs(y)

        ans = []
        dfs(self.king)
        return ans


# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

Continue Practicing

#1261 find elements in a contaminated binary tree #1993 operations on tree #1519 number of nodes in the sub tree with the same label