1600. Throne Inheritance

SourceWeekly Contest 208 Q3DifficultyMediumRating1768

Description

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.

Solutions

Solution 1: Preorder Traversal of a Multi-branch Tree

Thinking

The given \(\textit{Successor}\) walks to the oldest child not yet listed, then backtracks to the parent. Simulating that definition on every query rescans children lists; with up to \(10^5\) births the family can be large enough that each query becomes quadratic.

The same recurrence is a preorder walk of a multi-way tree: output the person, then recurse on children in birth order. Death does not reshape the tree — it only omits a name from the final list — so it suffices to store adjacency lists and a death set.

A hash table \(g\) records children in insertion order and a set \(\textit{dead}\) marks deaths. Birth and death are amortized \(O(1)\); \(\texttt{getInheritanceOrder}\) DFS from the king and appends living nodes in preorder.

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 \(\textit{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 \(\textit{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 \(\textit{birth}\) and \(\textit{death}\) have a time complexity of \(O(1)\), and \(\textit{getInheritanceOrder}\) has a time complexity of \(O(n)\). The space complexity is \(O(n)\), where \(n\) is the number of nodes.

Python3JavaC++GoTypeScriptC#

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.dead = set()
        self.g = defaultdict(list)

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

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

    def getInheritanceOrder(self) -> list[str]:
        def dfs(x: str):
            x not in self.dead and ans.append(x)
            for y in self.g[x]:
                dfs(y)

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


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

class ThroneInheritance {
    private String king;
    private Set<String> dead = new HashSet<>();
    private Map<String, List<String>> g = new HashMap<>();
    private List<String> ans = new ArrayList<>();

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

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

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

    public List<String> getInheritanceOrder() {
        ans.clear();
        dfs(king);
        return ans;
    }

    private void dfs(String x) {
        if (!dead.contains(x)) {
            ans.add(x);
        }
        for (String y : g.getOrDefault(x, List.of())) {
            dfs(y);
        }
    }
}

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

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

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

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

    vector<string> getInheritanceOrder() {
        ans.resize(0);
        dfs(king);
        return ans;
    }

private:
    string king;
    unordered_set<string> dead;
    unordered_map<string, vector<string>> g;
    vector<string> ans;

    void dfs(string& x) {
        if (!dead.contains(x)) {
            ans.emplace_back(x);
        }
        for (auto& y : g[x]) {
            dfs(y);
        }
    }
};

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance* obj = new ThroneInheritance(kingName);
 * obj->birth(parentName,childName);
 * obj->death(name);
 * vector<string> 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();
 */

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()
 */

public class ThroneInheritance {
    private string king;
    private HashSet<string> dead = new HashSet<string>();
    private Dictionary<string, List<string>> g = new Dictionary<string, List<string>>();
    private List<string> ans = new List<string>();

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

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

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

    public IList<string> GetInheritanceOrder() {
        ans.Clear();
        DFS(king);
        return ans;
    }

    private void DFS(string x) {
        if (!dead.Contains(x)) {
            ans.Add(x);
        }
        if (g.ContainsKey(x)) {
            foreach (string y in g[x]) {
                DFS(y);
            }
        }
    }
}

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

Solution 2: Explicit-Stack Preorder

Thinking

The given \(\textit{Successor}\) walks to the oldest child not yet listed, then backtracks to the parent. Simulating that definition on every query rescans children and becomes quadratic once the number of births reaches \(10^5\). The same recurrence is a preorder walk of a multi-way tree: write the person, then visit children in birth order. Death does not reshape the tree; it only omits a name. Recursion along a birth chain uses a call depth equal to the family size and overflows Python once the chain reaches length \(1000\). The query therefore uses a stack. A popped person is appended when still alive, and that person's children are pushed from last to first so the oldest child is popped next.

The inheritance order is a preorder traversal of a multi-way tree. A hash table \(g\) stores each person's children in birth order, and a set \(\textit{dead}\) stores the people who have died.

When calling birth(parentName, childName), append childName to the child list of parentName.
When calling death(name), add name to \(\textit{dead}\).
When calling getInheritanceOrder(), the stack starts with the king. After x is popped, append x when x is not in \(\textit{dead}\), then push the children of x from last to first so birth order is preserved.

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

Python3JavaC++GoTypeScriptC#

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.dead = set()
        self.g = defaultdict(list)

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

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

    def getInheritanceOrder(self) -> list[str]:
        ans = []
        stk = [self.king]
        while stk:
            x = stk.pop()
            if x not in self.dead:
                ans.append(x)
            for y in reversed(self.g[x]):
                stk.append(y)
        return ans


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

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

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

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

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

    public List<String> getInheritanceOrder() {
        List<String> ans = new ArrayList<>();
        Deque<String> stk = new ArrayDeque<>();
        stk.push(king);
        while (!stk.isEmpty()) {
            String x = stk.pop();
            if (!dead.contains(x)) {
                ans.add(x);
            }
            List<String> children = g.getOrDefault(x, List.of());
            for (int i = children.size() - 1; i >= 0; --i) {
                stk.push(children.get(i));
            }
        }
        return ans;
    }
}

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

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

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

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

    vector<string> getInheritanceOrder() {
        vector<string> ans;
        vector<string> stk{king};
        while (!stk.empty()) {
            string x = stk.back();
            stk.pop_back();
            if (!dead.contains(x)) {
                ans.emplace_back(x);
            }
            auto it = g.find(x);
            if (it == g.end()) {
                continue;
            }
            auto& children = it->second;
            for (int i = (int) children.size() - 1; i >= 0; --i) {
                stk.push_back(children[i]);
            }
        }
        return ans;
    }

private:
    string king;
    unordered_set<string> dead;
    unordered_map<string, vector<string>> g;
};

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance* obj = new ThroneInheritance(kingName);
 * obj->birth(parentName,childName);
 * obj->death(name);
 * vector<string> 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) {
    stk := []string{this.king}
    for len(stk) > 0 {
        x := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        if !this.dead[x] {
            ans = append(ans, x)
        }
        children := this.g[x]
        for i := len(children) - 1; i >= 0; i-- {
            stk = append(stk, children[i])
        }
    }
    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();
 */

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 stk: string[] = [this.king];
        while (stk.length) {
            const x = stk.pop()!;
            if (!this.dead.has(x)) {
                ans.push(x);
            }
            const children = this.g.get(x) || [];
            for (let i = children.length - 1; i >= 0; --i) {
                stk.push(children[i]);
            }
        }
        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()
 */

public class ThroneInheritance {
    private string king;
    private HashSet<string> dead = new HashSet<string>();
    private Dictionary<string, List<string>> g = new Dictionary<string, List<string>>();

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

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

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

    public IList<string> GetInheritanceOrder() {
        List<string> ans = new List<string>();
        Stack<string> stk = new Stack<string>();
        stk.Push(king);
        while (stk.Count > 0) {
            string x = stk.Pop();
            if (!dead.Contains(x)) {
                ans.Add(x);
            }
            if (g.ContainsKey(x)) {
                List<string> children = g[x];
                for (int i = children.Count - 1; i >= 0; --i) {
                    stk.Push(children[i]);
                }
            }
        }
        return ans;
    }
}

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

1600. Throne Inheritance

Description

Solutions

Solution 1: Preorder Traversal of a Multi-branch Tree

Solution 2: Explicit-Stack Preorder

Comments