Problem statement

A kingdom's line of succession lists the king first, then, for each of his children from oldest to youngest, that child followed by that child's whole line of succession — the same rule, applied again. A person who has died stays in the family tree (their descendants keep their place) but is left out of the list.

Write the class ThroneInheritance:

• ThroneInheritance(String kingName) starts the family with the king.
• void birth(String parentName, String childName) records that childName was born to parentName, as that parent's youngest child.
• void death(String name) records that name has died.
• String[] getInheritanceOrder() returns the current line of succession, living people only, in order.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

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"],[],["bob"],[]]
Output: [null,null,null,null,null,null,null,["king","andy","matthew","bob","alex","asha","catherine"],null,["king","andy","matthew","alex","asha","catherine"]]
Explanation: The order walks king, then andy and his son matthew, then bob and his children alex and asha, then catherine. When bob dies he leaves the list, but his children keep their places after matthew.

Example 2

Input: ["ThroneInheritance","death","birth","getInheritanceOrder"]
[["elena"],["elena"],["elena","noor"],[]]
Output: [null,null,null,["noor"]]
Explanation: The king can die too; his child noor is then first in line.

Constraints

• 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
• All names consist of lowercase English letters
• All names are distinct: no childName repeats an earlier name
• Every parentName and name passed to death already belongs to the family
• In every call to birth, parentName is alive
• At most 10^5 calls are made to birth and death
• At most 10 calls are made to getInheritanceOrder

Hints for Throne Inheritance

1. Hint 1

   The family is a tree: each person's children, in birth order. Keep a map from name to a list of children.

2. Hint 2

   The line of succession is exactly a pre-order traversal of that tree starting at the king, children visited oldest first.

3. Hint 3

   Deaths never change the tree — only who is printed. Keep a set of the dead and skip them during the traversal. (Use an explicit stack: the family can be a chain 10^5 people deep.)

How to solve Throne Inheritance

The succession rule is a pre-order walk of the family tree. Store the tree once, mark the dead in a set, and walk it when the order is asked for.

Approach

1. Keep children: name → list of children in birth order, and a set dead.
2. birth(parent, child): append child to children[parent]. death(name): add name to dead.
3. getInheritanceOrder(): walk the tree from the king in pre-order with a stack — pop a person, output them unless dead, then push their children youngest first so the oldest comes off next.

Why it works

The statement's rule — a person, then each child's whole line in age order — is the definition of a pre-order traversal with children in birth order. A death removes a person from the output but not from the tree, so their subtree is still visited in its place, exactly as the rule requires.

Complexity

• Time — O(1) per birth and death, O(n) per getInheritanceOrder for n people ever born
• Space — O(n)

Pitfalls

• Removing a dead person from the tree would orphan their descendants; only skip them when printing.
• Recursion on a chain of 10^5 people can overflow the call stack; an explicit stack avoids it.
• Children must be pushed youngest first so that the stack yields the oldest first.

Reference solution

Python

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.children = {}
        self.dead = set()

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

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

    def getInheritanceOrder(self) -> List[str]:
        order, stack = [], [self.king]
        while stack:  # pre-order walk, oldest child first
            p = stack.pop()
            if p not in self.dead:
                order.append(p)
            stack.extend(reversed(self.children.get(p, [])))
        return order

Java

class ThroneInheritance {
    private String king;
    private HashMap<String, List<String>> children = new HashMap<>();
    private HashSet<String> dead = new HashSet<>();

    public ThroneInheritance(String kingName) {
        king = kingName;
    }

    public void birth(String parentName, String childName) {
        children.computeIfAbsent(parentName, k -> new ArrayList<>()).add(childName);
    }

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

    public String[] getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push(king);
        while (!stack.isEmpty()) { // pre-order walk, oldest child first
            String p = stack.pop();
            if (!dead.contains(p)) order.add(p);
            List<String> c = children.get(p);
            if (c != null) for (int i = c.size() - 1; i >= 0; i--) stack.push(c.get(i));
        }
        return order.toArray(new String[0]);
    }
}

C++

class ThroneInheritance {
    string king;
    unordered_map<string, vector<string>> children;
    unordered_set<string> dead;
public:
    ThroneInheritance(string kingName) : king(kingName) {}

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

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

    vector<string> getInheritanceOrder() {
        vector<string> order, stack{king};
        while (!stack.empty()) { // pre-order walk, oldest child first
            string p = stack.back();
            stack.pop_back();
            if (!dead.count(p)) order.push_back(p);
            auto it = children.find(p);
            if (it != children.end())
                for (auto c = it->second.rbegin(); c != it->second.rend(); ++c) stack.push_back(*c);
        }
        return order;
    }
};

JavaScript

var ThroneInheritance = function(kingName) {
    this.king = kingName;
    this.children = new Map();
    this.dead = new Set();
};

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

ThroneInheritance.prototype.death = function(name) {
    this.dead.add(name);
};

ThroneInheritance.prototype.getInheritanceOrder = function() {
    var order = [], stack = [this.king];
    while (stack.length) { // pre-order walk, oldest child first
        var p = stack.pop();
        if (!this.dead.has(p)) order.push(p);
        var c = this.children.get(p) || [];
        for (var i = c.length - 1; i >= 0; i--) stack.push(c[i]);
    }
    return order;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium