Royal Succession: Determine the Order of Succession in a Family Tree After Removing Deceased Members

Question

## Problem

You are given a royal family tree. Succession follows pre-order traversal (depth-first, left-to-right). Implement two methods:

- `birth(parent, child)` -- add a child to a parent.
- `death(name)` -- mark a person as deceased.
- `order() -> list[str]` -- return the current line of succession (pre-order, excluding deceased).

```python
class RoyalSuccession:
    def birth(self, parent: str, child: str) -> None: ...
    def death(self, name: str) -> None: ...
    def order(self) -> list[str]: ...
```

**Example:**
```
rs.birth("King", "Alice")
rs.birth("King", "Bob")
rs.birth("Alice", "Carol")
rs.death("Alice")
rs.order() -> ["King", "Carol", "Bob"]
# Alice is dead but Carol (her child) still inherits before Bob
```

## Follow-ups
1. Why is pre-order (not in-order or post-order) the right traversal for succession?
2. How do you efficiently retrieve `order()` if `birth` and `death` are called millions of times?
3. Add `isKing(name) -> bool` that returns True if the given person is first in the succession line.
4. Handle the case where the root (current monarch) dies -- who automatically becomes monarch?

Royal Succession: Determine the Order of Succession in a Family Tree After Removing Deceased Members

Question Details

Full Details

Topics

More from Sofi