Adapt Throne Inheritance When Initialization Does Not Supply a King

Problem Statement

A kingdom tracks royal succession using a tree structure where order of succession is determined by a pre-order traversal starting from the monarch, excluding any members who have passed away. Unlike traditional royal registries, the kingdom starts in an uninitialized state where no founding monarch is specified upon creation.

Implement the ThroneInheritance class:

• ThroneInheritance(): Initializes the empty inheritance tracking system.
• crown_monarch(name: str) -> None: Crowns the founding monarch of the dynasty. This method must only be called once when the dynasty has no monarch. If a monarch has already been crowned, it should raise a ValueError.
• birth(parent_name: str, child_name: str) -> None: Records that parent_name gave birth to child_name. The parent_name must already exist in the dynasty (living or deceased). If called before a monarch is crowned or if parent_name does not exist, it should raise a ValueError.
• death(name: str) -> None: Marks name as deceased. If name does not exist in the dynasty, it should raise a ValueError. If name is already dead, the operation has no additional effect.
• get_inheritance_order() -> list[str]: Returns a list of names representing the current order of succession of living persons. If no monarch has been crowned, returns an empty list.

Succession Rules

Succession is evaluated via pre-order depth-first traversal:

1. The current person is visited first. If they are alive, they are appended to the succession list.
2. Their children are visited recursively in order of birth (oldest to youngest).

Examples

# Example 1
t = ThroneInheritance()
assert t.get_inheritance_order() == []

t.crown_monarch("king")
t.birth("king", "andy")
t.birth("king", "bob")
t.birth("andy", "catherine")
t.birth("andy", "matthew")
t.birth("bob", "alex")

# Pre-order: king -> andy -> catherine -> matthew -> bob -> alex
assert t.get_inheritance_order() == ["king", "andy", "catherine", "matthew", "bob", "alex"]

t.death("bob")
# bob is dead, skipped in succession order
assert t.get_inheritance_order() == ["king", "andy", "catherine", "matthew", "alex"]

t.death("king")
# king is dead, but succession order still roots at king
assert t.get_inheritance_order() == ["andy", "catherine", "matthew", "alex"]

Constraints

• 1 <= len(name) <= 15 for all name arguments.
• All names consist only of lowercase English letters.
• All names passed to crown_monarch and birth (as child_name) are unique.
• At most 10^5 total calls will be made across all methods.

Edge Cases

• Calling get_inheritance_order() before crown_monarch() should cleanly return [] without error.
• A deceased royal can still have children born after their death; their subtree remains in the succession line.
• Attempting to crown a monarch a second time or adding a child when no monarch exists must raise ValueError.