Maintain a Royal Family’s Succession Order

### Problem Implement `ThroneInheritance` for a changing family. Construction creates the monarch named `kingName`. `birth(parentName, childName)` appends a youngest child to that parent’s children. `death(name)` marks a person dead. `getInheritanceOrder()` returns the living people in succession order: visit a person, then that person’s children and all their descendants in birth order. Dead people are omitted from the result but their descendants keep their positions. ```cpp class ThroneInheritance { public: ThroneInheritance(string kingName); void birth(string parentName, string childName); void death(string name); vector<string> getInheritanceOrder(); }; ``` ### Examples **Example 1:** ```text ThroneInheritance t("ruler"); t.birth("ruler","iris"); t.birth("ruler","otto"); t.birth("iris","luna"); t.getInheritanceOrder() -> ["ruler","iris","luna","otto"] t.death("iris"); t.getInheritanceOrder() -> ["ruler","luna","otto"] ``` **Example 2:** ```text ThroneInheritance t("crown"); t.birth("crown","first"); t.death("crown"); t.getInheritanceOrder() -> ["first"] Explanation: Death omits the monarch but does not remove the child’s branch. ``` ### Constraints - All supplied names contain only lowercase English letters and have lengths in `[1,15]`. - The monarch’s name and every new child’s name are distinct. - A death refers to a person already introduced. A birth’s parent is alive. - At most `10^5` calls are made to birth and death; at most `10` calls query the order. ### Clarifying Questions The object persists between calls. Death is a mark, not deletion of a subtree. Children are ordered by birth calls, not by their names. ```hint Inspect the structure What must a succession query preserve after a death, including the positions of living descendants? ``` ### Reasoning checkpoints - Preserve birth order and the complete succession rules across repeated calls. - Keep living descendants in the correct place after an ancestor's death. - Keep the constructor and all three methods as the public protocol. ### Optional extensions What extra indexing would frequent succession queries require if returning a complete list were no longer necessary?