MediumHash TableTreeDepth-First SearchDesignUpdated Sep 2026

1600. Throne Inheritance

Asked at Snowflake

Difficulty

Medium

Time

O(1) for birth and death, O(n) f

Space

O(n)

Pattern

Hash Table

Companies

1

Problem

You are asked to design a class that models a royal family tree and answers questions about who inherits the throne.

The constructor gets the king's name. Then two updates arrive over time: birth(parentName, childName) says that parentName had a new child, and death(name) marks a person as dead. A dead person is not removed from the tree — their children still inherit through them — they are just skipped when you list the order.

The inheritance order is a preorder traversal of the family tree: start at the king, then take each child in the order they were born, and fully walk that child's line before moving to the next sibling. getInheritanceOrder() must return this list of names, leaving out everyone who is dead.

So birth and death are cheap bookkeeping, and the real work happens only when getInheritanceOrder() is called.

The family tree and its preorder order

catherineandymatthewkingalexbobdead → skippedashabob is dead, but his children alex and asha still inherit through himorderkingandymatthewbobalexashacatherine0123456bob stays in the position, but getInheritanceOrder drops him
Children are listed in birth order, and the inheritance order is a preorder walk that skips dead people.

Constraints

  • ●1 <= kingName.length, parentName.length, childName.length, name.length <= 15
  • ●kingName, parentName, childName, and name consist of lowercase English letters only
  • ●All arguments childName and kingName are distinct
  • ●All name arguments of death will be passed to either the constructor or as childName to birth first
  • ●For each call to birth(parentName, childName), parentName is guaranteed to be alive
  • ●At most 10^5 calls will be made to birth and death
  • ●At most 10 calls will be made to getInheritanceOrder

Examples

Example 1
Input["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"] [["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"],
Output[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]
WhyThe king's children are andy, bob, catherine in that birth order. Preorder means we take andy and his whole line first (matthew), then bob and his line (alex, asha), then catherine. After bob dies, he is skipped but his children alex and asha still appear in his place.
Example 2
Input["ThroneInheritance", "birth", "death", "getInheritanceOrder"] [["king"], ["king", "andy"], ["king"], [null]]
Output[null, null, null, ["andy"]]
WhyThe king is dead, so he is skipped. His son andy is still alive and is the only name returned.

Asked At

1 companies
CompanyDifficulty
SnowflakeMediumView all Snowflake questions →

How to Think About It

1

Store the family as a tree: a map from each person to the list of their children, appended in birth order.

2

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.

3

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.

4

birth and death are O(1); getInheritanceOrder is O(n) — the cost is pushed to the rare query operation.

5

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).

Iterative preorder with a stack

stackking← topStart with the king on the stackstackcatherinebobandy← topPop king, then push his children reversed so andy ison topstackcatherinebobmatthew← topPop andy, push his child matthew; matthew is visitednextpop p → if p not dead, append ppush children of p in reverse birth order
Push children in reverse so the oldest child is popped first, and skip dead names when popping.
ComplexityTime O(1) for birth and death, O(n) fSpace O(n)The cost comes from storing the tree and walking every person once when the order is requested.

What Trips People Up in Real Interviews

1

Implementing the recursive Successor function from the statement literally. Recognizing it as preorder is the whole point.

2

Deleting dead people from the tree, which loses their descendants' place in the line.

3

Pushing children onto the stack in birth order — they must be pushed in reverse so the eldest is popped first.

4

Recursing on a family line of 10^5 generations in Python without raising the recursion limit.

Solution Code

O(1) for birth and death, O(n) f time
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 order

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(1) for birth and death, O(n) f time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.