1600. Throne Inheritance - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

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.

Python

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

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

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

    def getInheritanceOrder(self) -> list:
        def dfs(person):
            if person not in self.deceased:
                order.append(person)
            for child in self.children[person]:
                dfs(child)

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

Java

import java.util.*;

class ThroneInheritance {
    Map<String, List<String>> children;
    Set<String> deceased;
    String king;

    public ThroneInheritance(String kingName) {
        king = kingName;
        children = new HashMap<>();
        deceased = new HashSet<>();
        children.put(king, new ArrayList<>());
    }

    public void birth(String parentName, String childName) {
        children.putIfAbsent(parentName, new ArrayList<>());
        children.get(parentName).add(childName);
    }

    public void death(String name) {
        deceased.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        dfs(king, order);
        return order;
    }

    private void dfs(String person, List<String> order) {
        if (!deceased.contains(person)) {
            order.add(person);
        }
        if (children.containsKey(person)) {
            for (String child : children.get(person)) {
                dfs(child, order);
            }
        }
    }
}

C++

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>

using namespace std;

class ThroneInheritance {
public:
    ThroneInheritance(string kingName) : king(kingName) {
        children.emplace(kingName, vector<string>());
    }

    void birth(string parentName, string childName) {
        children[parentName].emplace_back(childName);
    }

    void death(string name) {
        deceased.insert(name);
    }

    vector<string> getInheritanceOrder() {
        vector<string> order;
        dfs(king, order);
        return order;
    }

private:
    unordered_map<string, vector<string>> children;
    unordered_set<string> deceased;
    string king;

    void dfs(const string& person, vector<string>& order) {
        if (deceased.find(person) == deceased.end()) {
            order.push_back(person);
        }
        if (children.find(person) != children.end()) {
            for (const string& child : children[person]) {
                dfs(child, order);
            }
        }
    }
};

JavaScript

class ThroneInheritance {
    constructor(kingName) {
        this.king = kingName;
        this.children = new Map();
        this.children.set(kingName, []);
        this.deceased = new Set();
    }

    birth(parentName, childName) {
        if (!this.children.has(parentName)) {
            this.children.set(parentName, []);
        }
        this.children.get(parentName).push(childName);
    }

    death(name) {
        this.deceased.add(name);
    }

    getInheritanceOrder() {
        const order = [];
        const dfs = (person) => {
            if (!this.deceased.has(person)) {
                order.push(person);
            }
            if (this.children.has(person)) {
                for (const child of this.children.get(person)) {
                    dfs(child);
                }
            }
        };
        dfs(this.king);
        return order;
    }
}

using System;
using System.Collections.Generic;

public class ThroneInheritance {
    private Dictionary<string, List<string>> children;
    private HashSet<string> deceased;
    private string king;

    public ThroneInheritance(string kingName) {
        king = kingName;
        children = new Dictionary<string, List<string>>();
        deceased = new HashSet<string>();
        children[kingName] = new List<string>();
    }

    public void Birth(string parentName, string childName) {
        if (!children.ContainsKey(parentName)) {
            children[parentName] = new List<string>();
        }
        children[parentName].Add(childName);
    }

    public void Death(string name) {
        deceased.Add(name);
    }

    public IList<string> GetInheritanceOrder() {
        var order = new List<string>();
        Dfs(king, order);
        return order;
    }

    private void Dfs(string person, IList<string> order) {
        if (!deceased.Contains(person)) {
            order.Add(person);
        }
        if (children.ContainsKey(person)) {
            foreach (var child in children[person]) {
                Dfs(child, order);
            }
        }
    }
}

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.

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.

Python

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

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

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

    def getInheritanceOrder(self) -> list:
        def preorder(name):
            if name not in self.deceased:
                result.append(name)
            for child in self.family.get(name, []):
                preorder(child)

        result = []
        preorder(self.king)
        return result

Java

import java.util.*;

class ThroneInheritance {
    private Map<String, List<String>> familyTree;
    private Set<String> deceased;
    private String king;

    public ThroneInheritance(String kingName) {
        this.king = kingName;
        this.familyTree = new HashMap<>();
        this.deceased = new HashSet<>();
        this.familyTree.put(kingName, new ArrayList<>());
    }

    public void birth(String parentName, String childName) {
        familyTree.putIfAbsent(parentName, new ArrayList<>());
        familyTree.get(parentName).add(childName);
    }

    public void death(String name) {
        deceased.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> result = new ArrayList<>();
        dfs(king, result);
        return result;
    }

    private void dfs(String name, List<String> result) {
        if (!deceased.contains(name)) {
            result.add(name);
        }
        for (String child : familyTree.getOrDefault(name, new ArrayList<>())) {
            dfs(child, result);
        }
    }
}

C++

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>

using namespace std;

class ThroneInheritance {
public:
    ThroneInheritance(string kingName) {
        king = kingName;
        family[king] = {};
    }

    void birth(string parentName, string childName) {
        family[parentName].push_back(childName);
        family[childName] = {};
    }

    void death(string name) {
        deceased.insert(name);
    }

    vector<string> getInheritanceOrder() {
        vector<string> result;
        preorder(king, result);
        return result;
    }

private:
    unordered_map<string, vector<string>> family;
    unordered_set<string> deceased;
    string king;

    void preorder(const string &person, vector<string> &result) {
        if (deceased.find(person) == deceased.end()) {
            result.push_back(person);
        }
        for (string &child : family[person]) {
            preorder(child, result);
        }
    }
};

JavaScript

class ThroneInheritance {
    constructor(kingName) {
        this.kingName = kingName;
        this.children = new Map();
        this.deceased = new Set();
        this.children.set(kingName, []);
    }

    birth(parentName, childName) {
        if (!this.children.has(parentName)) {
            this.children.set(parentName, []);
        }
        this.children.get(parentName).push(childName);
        this.children.set(childName, []);
    }

    death(name) {
        this.deceased.add(name);
    }

    getInheritanceOrder() {
        const order = [];

        const preorder = (name) => {
            if (!this.deceased.has(name)) {
                order.push(name);
            }
            if (this.children.has(name)) {
                for (const child of this.children.get(name)) {
                    preorder(child);
                }
            }
        };

        preorder(this.kingName);
        return order;
    }
}

using System;
using System.Collections.Generic;

public class ThroneInheritance {
    private Dictionary<string, List<string>> familyTree;
    private HashSet<string> deceased;
    private string king;

    public ThroneInheritance(string kingName) {
        king = kingName;
        familyTree = new Dictionary<string, List<string>>();
        familyTree[king] = new List<string>();
        deceased = new HashSet<string>();
    }

    public void Birth(string parentName, string childName) {
        if (!familyTree.ContainsKey(parentName)) {
            familyTree[parentName] = new List<string>();
        }
        familyTree[parentName].Add(childName);
    }

    public void Death(string name) {
        deceased.Add(name);
    }

    public IList<string> GetInheritanceOrder() {
        var order = new List<string>();
        Dfs(king, order);
        return order;
    }

    private void Dfs(string person, IList<string> order) {
        if (!deceased.Contains(person)) {
            order.Add(person);
        }
        foreach (var child in familyTree.GetValueOrDefault(person, new List<string>())) {
            Dfs(child, order);
        }
    }
}

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.

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.

TypeScript

class ThroneInheritance {
    private king: string;
    private dead: Set<string> = new Set();
    private g: Map<string, string[]> = new Map();

    constructor(kingName: string) {
        this.king = kingName;
    }

    birth(parentName: string, childName: string): void {
        this.g.set(parentName, this.g.get(parentName) || []);
        this.g.get(parentName)!.push(childName);
    }

    death(name: string): void {
        this.dead.add(name);
    }

    getInheritanceOrder(): string[] {
        const ans: string[] = [];
        const dfs = (x: string) => {
            if (!this.dead.has(x)) {
                ans.push(x);
            }
            for (const y of this.g.get(x) || []) {
                dfs(y);
            }
        };
        dfs(this.king);
        return ans;
    }
}

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

type ThroneInheritance struct {
	king string
	dead map[string]bool
	g map[string][]string
}


func Constructor(kingName string) ThroneInheritance {
	return ThroneInheritance{kingName, map[string]bool{}, map[string][]string{}}
}


func (this *ThroneInheritance) Birth(parentName string, childName string)  {
	this.g[parentName] = append(this.g[parentName], childName)
}


func (this *ThroneInheritance) Death(name string)  {
	this.dead[name] = true
}


func (this *ThroneInheritance) GetInheritanceOrder() (ans []string) {
	var dfs func(string)
	dfs = func(x string) {
		if !this.dead[x] {
			ans = append(ans, x)
		}
		for _, y := range this.g[x] {
			dfs(y)
		}
	}
	dfs(this.king)
	return
}


/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * obj := Constructor(kingName);
 * obj.Birth(parentName,childName);
 * obj.Death(name);
 * param_3 := obj.GetInheritanceOrder();
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
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	–

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

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.

Throne Inheritance solution and explanation

The problem

Approach overview

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

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

Approach 3: Preorder Traversal of a Multi-branch Tree

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Throne Inheritance solution and explanation

The problem

Approach overview

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

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

Approach 3: Preorder Traversal of a Multi-branch Tree

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems