Watch 7 video solutions for Throne Inheritance, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by Naresh Gupta has 1,154 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A kingdom consists of a king, his children, his grandchildren, and so on. Every once in a while, someone in the family dies or a child is born.
The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let's define the recursive function Successor(x, curOrder), which given a person x and the inheritance order so far, returns who should be the next person after x in the order of inheritance.
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
For example, assume we have a kingdom that consists of the king, his children Alice and Bob (Alice is older than Bob), and finally Alice's son Jack.
curOrder will be ["king"].Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].Successor(Bob, curOrder) will return null. Thus the order of inheritance will be ["king", "Alice", "Jack", "Bob"].Using the above function, we can always obtain a unique order of inheritance.
Implement the ThroneInheritance class:
ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.void birth(string parentName, string childName) Indicates that parentName gave birth to childName.void death(string name) Indicates the death of name. The death of the person doesn't affect the Successor function nor the current inheritance order. You can treat it as just marking the person as dead.string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.
Example 1:
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 <= 15kingName, parentName, childName, and name consist of lowercase English letters only.childName and kingName are distinct.name arguments of death will be passed to either the constructor or as childName to birth first.birth(parentName, childName), it is guaranteed that parentName is alive.105 calls will be made to birth and death.10 calls will be made to getInheritanceOrder.Problem Overview: You design a system that models a royal family. The king starts the lineage. New children are born to existing members, some members die, and you must return the current inheritance order. The order follows standard monarchy rules: a parent appears before their children, and children are processed in birth order while skipping deceased members.
Approach 1: Depth-First Search for Inheritance Order (O(n) time, O(n) space)
The core observation is that inheritance order follows a pre-order DFS traversal of the family tree. Maintain a HashMap from a person's name to a list of their children (stored in birth order). Track deaths using a HashSet. When getInheritanceOrder() is called, start from the king and run DFS: add a person to the result if they are alive, then recursively process their children. This traversal naturally respects the rule that descendants appear immediately after their parent. Time complexity for generating the order is O(n), where n is the total number of people in the lineage, and space complexity is O(n) for the tree structure and recursion stack. This approach directly models the hierarchy using a tree and uses depth-first search to produce the final sequence.
Approach 2: Pre-order Traversal with Tree-like Structure (O(n) time, O(n) space)
Another implementation keeps an explicit node-like structure representing each family member. Each node stores the person's name and a list of children in birth order. Maintain a HashMap that maps names to their corresponding nodes so births can append children in O(1). Deaths are recorded using a boolean flag or a HashSet. When generating the inheritance order, perform a pre-order traversal starting from the king node and skip any nodes marked as dead. The traversal visits each node exactly once, so order generation takes O(n) time with O(n) auxiliary space for recursion and the resulting list. This design emphasizes object relationships and fits naturally with problems tagged under design and hash table.
Recommended for interviews: The DFS-based family tree approach is what most interviewers expect. Modeling births as edges in a tree and generating order with a pre-order traversal shows you understand hierarchical structures and traversal patterns. A brute-force list reconstruction would work but becomes messy as the lineage grows. Using a tree plus DFS keeps operations simple and produces the correct inheritance order in linear time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search for Inheritance Order | O(n) | O(n) | Standard implementation; simple family tree + DFS traversal |
| Pre-order Traversal with Tree-like Structure | O(n) | O(n) | Object-oriented design where each member is stored as a node |