Throne Inheritance - Video Solutions

MediumHash TableTreeDepth-First SearchDesign

Practice this problem Read Solution

throne inheritance | throne inheritance leetcode | leetcode 1600 | dfs

10:031,187 views

8 video solutions available

Throne Inheritance - Video Solution

Watch 8 video solutions for Throne Inheritance, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by Naresh Gupta has 1,187 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

Problem Statement

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.

In the beginning, curOrder will be ["king"].
Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get ["king", "Alice"].
Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get ["king", "Alice", "Jack"].
Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get ["king", "Alice", "Jack", "Bob"].
Calling 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 <= 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 10⁵ calls will be made to birth and death.
At most 10 calls will be made to getInheritanceOrder.

Read full problem with examples

Approach Overview

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.

Complexity Analysis

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

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough