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.

  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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

**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.

Solution

Method 1 - Tree with DFS Traversal

We use a tree to represent the family, with each node storing the children in birth order. We use a set to track dead people. The inheritance order is obtained by a DFS pre-order traversal, skipping dead people.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;

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;
        dfs(king, order);
        return order;
    }
    void dfs(const string& name, vector<string>& order) {
        if (!dead.count(name)) order.push_back(name);
        for (const string& child : children[name]) dfs(child, order);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;
public class ThroneInheritance {
    private String king;
    private Map<String, List<String>> children = new HashMap<>();
    private Set<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 List<String> getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        dfs(king, order);
        return order;
    }
    private void dfs(String name, List<String> order) {
        if (!dead.contains(name)) order.add(name);
        for (String child : children.getOrDefault(name, Collections.emptyList())) {
            dfs(child, order);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

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

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

    def getInheritanceOrder(self) -> list[str]:
        order = []
        def dfs(name):
            if name not in self.dead:
                order.append(name)
            for child in self.children.get(name, []):
                dfs(child)
        dfs(self.king)
        return order
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

use std::collections::{HashMap, HashSet};
pub struct ThroneInheritance {
    king: String,
    children: HashMap<String, Vec<String>>,
    dead: HashSet<String>,
}
impl ThroneInheritance {
    pub fn new(king_name: String) -> Self {
        Self { king: king_name, children: HashMap::new(), dead: HashSet::new() }
    }
    pub fn birth(&mut self, parent_name: String, child_name: String) {
        self.children.entry(parent_name).or_default().push(child_name);
    }
    pub fn death(&mut self, name: String) {
        self.dead.insert(name);
    }
    pub fn get_inheritance_order(&self) -> Vec<String> {
        let mut order = vec![];
        fn dfs(name: &str, children: &HashMap<String, Vec<String>>, dead: &HashSet<String>, order: &mut Vec<String>) {
            if !dead.contains(name) {
                order.push(name.to_string());
            }
            if let Some(kids) = children.get(name) {
                for child in kids {
                    dfs(child, children, dead, order);
                }
            }
        }
        dfs(&self.king, &self.children, &self.dead, &mut order);
        order
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class ThroneInheritance {
    private king: string;
    private children: Map<string, string[]> = new Map();
    private dead: Set<string> = new Set();
    constructor(kingName: string) {
        this.king = kingName;
    }
    birth(parentName: string, childName: string): void {
        if (!this.children.has(parentName)) this.children.set(parentName, []);
        this.children.get(parentName)!.push(childName);
    }
    death(name: string): void {
        this.dead.add(name);
    }
    getInheritanceOrder(): string[] {
        const order: string[] = [];
        const dfs = (name: string) => {
            if (!this.dead.has(name)) order.push(name);
            for (const child of this.children.get(name) || []) dfs(child);
        };
        dfs(this.king);
        return order;
    }
}

Complexity

  • ⏰ Time complexity: O(N) for each getInheritanceOrder (N = number of people)
  • 🧺 Space complexity: O(N)