Throne Inheritance
Asked at Snowflake
Problem
Throne Inheritance asks you to model a royal family: record births and deaths, and return the current order of succession. The succession order turns out to be exactly a preorder traversal of the family tree (children in birth order), skipping anyone who has died.
Asked At
| Company | Difficulty | |
|---|---|---|
| Snowflake | Medium | View all Snowflake questions → |
How to Think About It
Store the family as a tree: a map from each person to the list of their children, appended in birth order.
Key insight: the order of inheritance is a preorder traversal — the king, then his first child and that child's entire line, then his second child and their line, and so on.
Deaths do not remove people from the tree (their descendants still inherit through them). Keep a dead set and simply skip dead people when building the order.
birth and death are O(1); getInheritanceOrder is O(n) — the cost is pushed to the rare query operation.
Use an iterative DFS with a stack (pushing children in reverse) to avoid recursion depth limits on long family lines.
Optimal Approach
State: king, children map, dead set.
birth(parent, child): append child to children[parent].death(name): add name to dead.getInheritanceOrder(): preorder DFS from king, adding each person not in dead; visit children in the order they were born.
Time: O(1) for birth and death, O(n) for the order. Space: O(n).
What Trips People Up in Real Interviews
Implementing the recursive Successor function from the statement literally. Recognizing it as preorder is the whole point.
Deleting dead people from the tree, which loses their descendants' place in the line.
Pushing children onto the stack in birth order — they must be pushed in reverse so the eldest is popped first.
Recursing on a family line of 10^5 generations in Python without raising the recursion limit.
Solution Code
class ThroneInheritance:
def __init__(self, kingName):
self.king = kingName
self.children = {}
self.dead = set()
def birth(self, parentName, childName):
self.children.setdefault(parentName, []).append(childName)
def death(self, name):
self.dead.add(name)
def getInheritanceOrder(self):
order = []
stack = [self.king]
while stack:
p = stack.pop()
if p not in self.dead:
order.append(p)
stack.extend(reversed(self.children.get(p, [])))
return orderFrequently Asked Questions
What is the Throne Inheritance problem?
Throne Inheritance asks you to model a royal family: record births and deaths, and return the current order of succession. The succession order turns out to be exactly a preorder traversal of the family tree (children in birth order), skipping anyone who has died.
How do you solve Throne Inheritance?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Throne Inheritance?
Throne Inheritance is asked at Snowflake. It is a medium difficulty problem.
What are common mistakes on Throne Inheritance?
- Implementing the recursive `Successor` function from the statement literally. Recognizing it as preorder is the whole point.
- Deleting dead people from the tree, which loses their descendants' place in the line.
- Pushing children onto the stack in birth order — they must be pushed in reverse so the eldest is popped first.
- Recursing on a family line of 10^5 generations in Python without raising the recursion limit.