Throne Inheritance

medium tree dfs design

Problem

A kingdom is a family tree rooted at the king: each person has an ordered list of children. Births and deaths happen over time. getInheritanceOrder() returns the current order of inheritance — a pre-order walk from the king (visit a person, then recurse into their children oldest-first) — while skipping anyone who has died.

Inputking with children andy, bob, catherine; andy→matthew; bob→alex, asha; death(bob)

Output["king","andy","matthew","alex","asha","catherine"]

Pre-order visits king, andy, matthew, bob, alex, asha, catherine; bob is dead, so it is dropped.

births (parent>child, comma-separated)

deaths (names, comma-separated)

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

    def birth(self, parent, child):
        self.children.setdefault(parent, []).append(child)

    def death(self, name):
        self.dead.add(name)

    def getInheritanceOrder(self):
        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

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

class ThroneInheritance {
    String king;
    Map<String, List<String>> children = new HashMap<>();
    Set<String> dead = new HashSet<>();
    public ThroneInheritance(String king) { this.king = king; }
    public void birth(String parent, String child) {
        children.computeIfAbsent(parent, k -> new ArrayList<>()).add(child);
    }
    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, List.of())) dfs(child, order);
    }
}

class ThroneInheritance {
    string king;
    unordered_map<string, vector<string>> children;
    unordered_set<string> dead;
    void dfs(const string& name, vector<string>& order) {
        if (!dead.count(name)) order.push_back(name);
        for (auto& child : children[name]) dfs(child, order);
    }
public:
    ThroneInheritance(string kingName) : king(kingName) {}
    void birth(string parent, string child) { children[parent].push_back(child); }
    void death(string name) { dead.insert(name); }
    vector<string> getInheritanceOrder() {
        vector<string> order;
        dfs(king, order);
        return order;
    }
};

Explanation

The family forms a tree: the king is the root and every birth(parent, child) appends a child to its parent's ordered list. We store this as a map children from a name to its list of kids, plus a dead set to mark people who have died.

The inheritance order is exactly a pre-order DFS from the king. Pre-order means: record the current person first, then recurse into each child in birth order. This naturally produces the recursive Successor rule from the prompt — a person is followed by their oldest unseen child, and once a whole subtree is done we back up to the next sibling.

Death never changes the tree shape or the traversal — it only flips a flag. So during the DFS we still descend through a dead person to reach their descendants, but we simply do not append the dead person's own name to the output.

Births and deaths are O(1) hash operations. Only getInheritanceOrder is heavy, visiting all n people once, which is why the problem caps it to a handful of calls.

Example: with bob dead, the walk king → andy → matthew → bob → alex → asha → catherine drops bob, giving ["king","andy","matthew","alex","asha","catherine"].

Time: O(n) per getInheritanceOrder Space: O(n)