# Throne Inheritance
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/throne-inheritance)
Canonical: https://scaleengineer.com/dsa/problems/throne-inheritance
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Hash Table, Tree
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## 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.

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

# Approaches
## Simulating the Successor Function
This approach directly implements the logic described by the `Successor` function in the problem description. We maintain the family tree structure, including parent-child relationships. When `getInheritanceOrder` is called, we start with the king and iteratively find the next successor until the entire inheritance order is generated. This process involves repeatedly searching for the next eligible heir by traversing down to children and backtracking to parents, as defined by the `Successor` logic.
**Time:** `birth` and `death` are O(1). `getInheritanceOrder` is O(N*H) where N is the number of people and H is the height of the family tree. In the worst case of a skewed tree, H=N, leading to O(N^2) time complexity due to the costly `findSuccessor` calls. · **Space:** O(N), where N is the number of people in the kingdom. This space is used to store the kingdom map, the person objects with their parent/child references, and the set for the current order during generation.
**Pros:** It is a direct and literal translation of the problem's recursive definition, making it conceptually straightforward to derive from the problem statement.
**Cons:** The `getInheritanceOrder` method is inefficient due to repeated traversals of the tree.; Requires storing parent pointers for each person, which adds complexity and memory overhead.
### Explanation
We'll use a `Map` to associate names with custom `Person` objects. Each `Person` object will store their name, a list of their children, a reference to their parent, and their living status. This structure allows us to navigate both down (to children) and up (to parents) the family tree.

The `birth` method adds a new `Person` to the tree, linking them to their parent. The `death` method marks a person as deceased.

The `getInheritanceOrder` method builds the inheritance list one person at a time by simulating the `Successor` function. It starts with the king and in a loop, calls a recursive `findSuccessor` helper. This helper, given a person `x`, first checks `x`'s children for the next heir. If none are found, it backtracks to `x`'s parent and continues the search from there. This continues until the entire line of succession is found. Finally, the generated list is filtered to exclude the dead.

This approach is slow because finding each successor can involve traversing significant portions of the tree multiple times. For instance, after processing a leaf node, the algorithm must backtrack up the tree, potentially re-scanning children at each level.

```java
class ThroneInheritance {
    class Person {
        String name;
        List<Person> children = new ArrayList<>();
        Person parent;
        boolean isAlive = true;

        Person(String name) {
            this.name = name;
        }
    }

    Map<String, Person> kingdom = new HashMap<>();
    Person king;

    public ThroneInheritance(String kingName) {
        king = new Person(kingName);
        kingdom.put(kingName, king);
    }

    public void birth(String parentName, String childName) {
        Person p = kingdom.get(parentName);
        Person c = new Person(childName);
        p.children.add(c);
        c.parent = p;
        kingdom.put(childName, c);
    }

    public void death(String name) {
        kingdom.get(name).isAlive = false;
    }

    public List<String> getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        Set<String> inOrderSet = new HashSet<>();

        order.add(king.name);
        inOrderSet.add(king.name);

        String lastPersonName = king.name;
        while (true) {
            Person lastPersonNode = kingdom.get(lastPersonName);
            String successorName = findSuccessor(lastPersonNode, inOrderSet);
            if (successorName == null) {
                break;
            }
            order.add(successorName);
            inOrderSet.add(successorName);
            lastPersonName = successorName;
        }

        List<String> livingOrder = new ArrayList<>();
        for (String name : order) {
            if (kingdom.get(name).isAlive) {
                livingOrder.add(name);
            }
        }
        return livingOrder;
    }

    private String findSuccessor(Person p, Set<String> inOrderSet) {
        for (Person child : p.children) {
            if (!inOrderSet.contains(child.name)) {
                return child.name;
            }
        }
        if (p == king) {
            return null;
        }
        return findSuccessor(p.parent, inOrderSet);
    }
}
```
### Algorithm
- Use a `Map<String, Person>` to store `Person` objects, allowing quick access by name. Each `Person` object stores their name, a list of children (`List<Person>`), a reference to their parent (`Person`), and a boolean `isAlive`.
- `ThroneInheritance(kingName)`: Create the king `Person` object and initialize the map.
- `birth(parentName, childName)`: Look up the parent `Person` object. Create a new `Person` object for the child. Add the child to the parent's children list and set the child's parent reference. Add the new child to the kingdom map.
- `death(name)`: Look up the `Person` object by name and set their `isAlive` flag to `false`.
- `getInheritanceOrder()`:
    1. Create an empty list `fullOrder` and a `HashSet<String> inOrder` for efficient lookups. Add the king to both.
    2. Start with `lastAdded = king.name`.
    3. Enter a loop that repeatedly calls a recursive helper function `findSuccessor(kingdom.get(lastAdded), inOrder)`.
    4. If the successor is `null`, break the loop. Otherwise, add the successor's name to `fullOrder` and `inOrder`, and update `lastAdded` to this new name.
    5. After the loop, filter `fullOrder` to create a new list containing only living people.
- `findSuccessor(person, inOrder)` (recursive helper):
    1. Iterate through `person`'s children. If a child is found whose name is not in `inOrder`, return that child's name.
    2. If all children are processed, backtrack by recursively calling `findSuccessor` on `person`'s parent, unless `person` is the king.

## Pre-order Traversal (Depth-First Search)
The inheritance order described in the problem is equivalent to a pre-order traversal of the family tree. A pre-order traversal visits the current node first, then recursively visits its children from oldest to youngest. This approach leverages this observation for a much more efficient implementation. We build the family tree and then perform a single Depth-First Search (DFS) starting from the king to generate the inheritance order.
**Time:** `birth` and `death` are O(1) on average. `getInheritanceOrder` is O(N), where N is the total number of people in the kingdom, as it performs a single traversal of the entire family tree. · **Space:** O(N), where N is the number of people. This space is required for the `familyTree` map, the `dead` set, and the recursion stack for the DFS (which can be up to O(N) in the worst case of a skewed tree).
**Pros:** Highly efficient `getInheritanceOrder` with a time complexity linear in the number of people.; The implementation is simple and clean.; It does not require storing parent pointers, which saves space and reduces complexity.
**Cons:** This approach relies on recognizing that the inheritance order is a pre-order traversal, which might not be immediately obvious from the problem's recursive definition of `Successor`.
### Explanation
We can represent the family tree using a `Map<String, List<String>>`, where each key is a person's name and the value is an ordered list of their children's names. A `Set<String>` is used to efficiently keep track of people who have died.

The `birth` method simply adds a child to the parent's list of children in the map. The `death` method adds the person's name to the `dead` set.

The key insight is that the `getInheritanceOrder` method can be implemented by performing a single pre-order traversal (which can be done with a Depth-First Search) on the tree structure.
1. We start a recursive DFS function from the king.
2. The DFS function takes the current person's name as an argument.
3. Inside the function, we first check if the current person is alive (i.e., not in the `dead` set). If they are, we add their name to our result list. This is the "visit" step in the pre-order traversal.
4. Then, we retrieve the list of their children from our map and iterate through them in order, making a recursive DFS call for each child.

This process naturally builds the inheritance list in the correct sequence in a single pass over the tree, making it very efficient.

```java
class ThroneInheritance {
    private Map<String, List<String>> familyTree;
    private Set<String> dead;
    private String kingName;

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

    public void birth(String parentName, String childName) {
        familyTree.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(kingName, order);
        return order;
    }

    private void dfs(String name, List<String> order) {
        // Pre-order traversal: Visit node, then visit children.
        // 1. Visit node: Add to order if alive.
        if (!dead.contains(name)) {
            order.add(name);
        }

        // 2. Visit children: Recursively call dfs for each child.
        List<String> children = familyTree.getOrDefault(name, new ArrayList<>());
        for (String child : children) {
            dfs(child, order);
        }
    }
}
```
### Algorithm
- Use a `Map<String, List<String>>` to represent the family tree. The key is the parent's name, and the value is a list of their children's names in birth order.
- Use a `Set<String>` to store the names of deceased people for O(1) average time lookups.
- `ThroneInheritance(kingName)`: Store the `kingName`, initialize the map and the set. Add the king to the map with an empty list of children.
- `birth(parentName, childName)`: Use `map.computeIfAbsent(parentName, ...).add(childName)` to add the new child to the parent's list of children.
- `death(name)`: Add the name to the `dead` set.
- `getInheritanceOrder()`:
    1. Initialize an empty `ArrayList<String>` to store the result.
    2. Call a recursive DFS helper function, `dfs(kingName, resultList)`.
    3. Return the `resultList`.
- `dfs(currentPersonName, resultList)` (recursive helper):
    1. Check if `currentPersonName` is in the `dead` set. If not, add it to `resultList` (this is the pre-order visit).
    2. Get the list of children for `currentPersonName` from the map.
    3. For each `childName` in the list, make a recursive call: `dfs(childName, resultList)`.

# Solutions
### CSharp

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

### Java

```java
class ThroneInheritance { private Map < String , List < String >> g = new HashMap <>(); private Set < String > dead = new HashSet <>(); private List < String > ans ; private String king ; 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 = new ArrayList <>(); dfs ( king ); return ans ; } private void dfs ( String x ) { if (! dead . contains ( x )) { ans . add ( x ); } for ( String y : g . getOrDefault ( x , Collections . emptyList ())) { 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(); */
```

### CPP

```cpp
class ThroneInheritance { public: unordered_map < string , vector < string >> g ; unordered_set < string > dead ; string king ; vector < string > ans ; ThroneInheritance ( string kingName ) { king = kingName ; } void birth ( string parentName , string childName ) { g [ parentName ]. push_back ( childName ); } void death ( string name ) { dead . insert ( name ); } vector < string > getInheritanceOrder () { ans . resize ( 0 ); dfs ( king ); return ans ; } void dfs ( string & x ) { if ( ! dead . count ( x )) { ans . push_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(); */
```

### Python

```python
class ThroneInheritance : def __init__ ( self , kingName : str ): self . g = defaultdict ( list ) self . dead = set () self . king = kingName 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 ): if x not in self . dead : 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()
```