Skip to main content
Talentd

Throne Inheritance - Solution & Explanation

MediumHash TableTreeDepth-First SearchDesign22 min readAsked at: Snowflake, Google
Practice this problem

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.

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

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.

Approach 1: Approach 1: Depth-First Search for Inheritance Order

In this approach, we treat the kingdom hierarchy as a tree, with the king as the root. Each node represents a person and children of the node are immediate descendents (children) in the order of their birth. To find the inheritance order, we use a Depth-First Search (DFS) starting from the king. Each time a person is visited, if they are not marked as dead, they are added to the inheritance result list.

This solution implements the ThroneInheritance class using Python. It manages the family tree using a dictionary where each key is a person's name, and the value is a list of their children's names. The 'birth' function adds a child to the parent's list of children. The 'death' function simply marks a person as deceased by adding them to a set. Finally, the 'getInheritanceOrder' performs a DFS starting from the king and collects the names of all living people according to inheritance rules.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of people in the kingdom because each person is visited only once during DFS. Space Complexity: O(N) for storing child relationships and tracking deceased people.

Try this approach in the editor →

Approach 2: Approach 2: Pre-order Traversal with Tree-like Structure

Consider the family as a tree with a pre-order traversal to determine the inheritance order. We constantly track the parent-child relationships and use a set to mark deceased individuals. The order is generated through recursive traversal excluding deceased members at each step.

This code in Python utilizes pre-order traversal to track the inheritance order. By storing relationships in a dictionary and deceased statuses in a set, it ensures that as names are entered, they are registered properly in the hierarchy setup. The inheritance order is then collected via recursive pre-order traversal, omitting deceased family members.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(N) for traversal of the entire family structure and assembly of the order. Space Complexity: O(N) is required for storing hierarchical information and deceased statuses using a dictionary and set.

Try this approach in the editor →

Approach 3: 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.

  • When calling birth(parentName, childName), we add childName to the child list of parentName.
  • When calling death(name), we add name to the dead set.
  • When calling getInheritanceOrder(), we start a depth-first search from the king. If the current node x is not dead, we add x to the answer list, and then recursively traverse all children of x.

In terms of time complexity, both birth and death have a time complexity of O(1), and getInheritanceOrder has a time complexity of O(n). The space complexity is O(n), where n is the number of nodes.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Depth-First Search for Inheritance Order

Time Complexity: O(N), where N is the number of people in the kingdom because each person is visited only once during DFS. Space Complexity: O(N) for storing child relationships and tracking deceased people.

Approach 2: Pre-order Traversal with Tree-like Structure

Time Complexity: O(N) for traversal of the entire family structure and assembly of the order. Space Complexity: O(N) is required for storing hierarchical information and deceased statuses using a dictionary and set.

Preorder Traversal of a Multi-branch Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search for Inheritance OrderO(n)O(n)Standard implementation; simple family tree + DFS traversal
Pre-order Traversal with Tree-like StructureO(n)O(n)Object-oriented design where each member is stored as a node

Video Solution

throne inheritance | throne inheritance leetcode | leetcode 1600 | dfs • Naresh Gupta • 1,187 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Throne Inheritance easy or hard?
Throne Inheritance is generally considered a medium-level problem. The difficulty comes from modeling the family structure correctly and realizing that the inheritance order is simply a pre-order traversal of the tree while skipping deceased members. Once the structure is built, the traversal logic is straightforward.
How to solve Throne Inheritance in O(n)?
Store the family hierarchy as an adjacency list where each person maps to their children. Record deaths in a hash set. When getInheritanceOrder is called, perform a pre-order DFS starting from the king, adding only living members to the result list. Since every node is visited once, the operation runs in O(n) time.
What is the best approach for Throne Inheritance?
The most common solution models the royal family as a tree and generates the inheritance order using a pre-order depth-first search. A hash map stores each person's children in birth order, and a set tracks deceased members. When retrieving the order, DFS starts from the king and skips anyone marked as dead. This produces the correct succession order in O(n) time.
Is Throne Inheritance asked at Google/Amazon/Meta?
Throne Inheritance is a design-style tree traversal problem commonly seen in interviews at large tech companies. Variations involving hierarchical structures, DFS traversal, and system design patterns appear in interviews at companies like Amazon, Google, and Meta. The problem tests both data structure modeling and traversal logic.
What data structure is used in Throne Inheritance?
The primary data structure is a tree representing the family lineage. A hash map maps each person to a list of their children to preserve birth order, while a hash set or boolean flag records deaths. Depth-first search is then used to compute the inheritance sequence.
What is the time complexity of Throne Inheritance?
Generating the inheritance order takes O(n) time because each person in the family tree is visited once during the DFS traversal. Birth and death operations are typically O(1) using a hash map and set. Space complexity is O(n) for storing the family tree structure and death records.
Throne Inheritance Python or Java solution approach
Both Python and Java implementations typically use a hash map to store children lists and a set to track deceased members. The getInheritanceOrder function runs a recursive DFS or iterative traversal starting from the king. The logic remains identical across languages with O(n) traversal time.

Ready to solve this problem?

Practice Throne Inheritance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Operations on Tree