Throne Inheritance: Tree Design with Pre-Order DFS

You need to design a system that models a royal family tree. The king starts at the root. People are born (added as children of their parent), people die (marked but not removed), and at any point you can query the current inheritance order. The order follows a pre-order DFS: the king comes first, then recursively each of the king's children (in birth order) and their subtrees, skipping anyone who is dead.

This is LeetCode 1600: Throne Inheritance, and it is a design problem where the core algorithm is just pre-order tree traversal.

Why this problem matters

This problem tests whether you can design a clean data structure that maps a real-world concept (family hierarchy) to a well-known algorithm (pre-order DFS). It sits at the intersection of two important skills: system design and tree traversal.

In real software, you encounter problems like this constantly. Organization charts, file systems, comment threads, and category hierarchies are all trees. The operations are always the same: add a node, remove a node, and traverse the tree in some order. Throne Inheritance isolates these operations in a clean LeetCode wrapper so you can practice them.

The pre-order DFS pattern here is the same one you use to serialize a tree, generate a table of contents from nested headings, or walk a DOM. Mastering it in this context means you can apply it everywhere.

The key insight

The family tree is an N-ary tree (each person can have any number of children). The inheritance order is just a pre-order traversal of this tree, with dead members filtered out.

That means you need two things:

1. A way to look up any person's children in birth order. A hash map from name to list of children handles this.
2. A way to check if someone is dead. A set of dead names handles this.

The birth operation appends a child to a parent's list. The death operation adds a name to the dead set. The getInheritanceOrder operation runs a pre-order DFS from the king, collecting every name that is not in the dead set.

There is no need to actually delete nodes from the tree when someone dies. Dead people still have children who might be alive, so you must traverse through them. You just skip adding their name to the output.

The solution

class ThroneInheritance:
    def __init__(self, kingName: str):
        self.king = kingName
        self.children = {kingName: []}
        self.dead = set()

    def birth(self, parentName: str, childName: str) -> None:
        self.children.setdefault(parentName, [])
        self.children[parentName].append(childName)
        self.children.setdefault(childName, [])

    def death(self, name: str) -> None:
        self.dead.add(name)

    def getInheritanceOrder(self) -> list[str]:
        order = []
        def dfs(name):
            if name not in self.dead:
                order.append(name)
            for child in self.children.get(name, []):
                dfs(child)
        dfs(self.king)
        return order

Let's break this down.

__init__ stores the king's name and initializes the children dictionary with an empty list for the king. The dead set starts empty.

birth takes a parent name and a child name. It appends the child to the parent's children list. It also initializes an empty children list for the new child (so they can have children later). The setdefault calls ensure we never get a KeyError.

death simply adds the name to the dead set. We do not remove the person from the tree. Their subtree still needs to be traversed because their descendants might be alive.

getInheritanceOrder runs a recursive pre-order DFS starting from the king. At each node, if the person is not dead, add them to the output. Then recurse into each child in order. The recursion naturally visits the entire subtree of each child before moving to the next sibling, which is exactly the pre-order traversal that defines the inheritance order.

Visual walkthrough

Let's trace through the full sequence of operations. We start with the king, add children with birth, mark Bob as dead with death, and then call getInheritanceOrder to see how the DFS skips Bob while still visiting the rest of the tree.

Notice how Bob's position in the tree still matters. Even though Bob is dead, the DFS visits his node in the correct position between Andy's subtree and Catherine's subtree. If Bob had children, they would appear right after Bob's position in the traversal. Bob himself is just skipped in the output.

Complexity analysis

Let n be the total number of people (alive and dead) in the family tree.

birth is O(1) amortized. It appends to a list and does a dictionary lookup. Both are constant time.

death is O(1). It adds a name to a set.

getInheritanceOrder is O(n). The DFS visits every node exactly once. The output list can hold up to n names. The recursion stack can go up to O(n) deep in the worst case (a single chain of parent-child relationships).

Space for the entire data structure is O(n). The children dictionary stores every person, and each person appears in exactly one parent's children list. The dead set can hold at most n names.

The building blocks

This problem is built from two reusable pieces that CodeBricks drills independently:

1. N-ary tree representation with a hash map

Storing a tree where each node can have any number of children:

children = {kingName: []}

def birth(parent, child):
    children.setdefault(parent, [])
    children[parent].append(child)
    children.setdefault(child, [])

This is the adjacency list pattern applied to trees. Instead of storing tree nodes as objects with pointers, you store the parent-to-children mapping in a dictionary. This representation is common in problems where nodes are identified by name or ID rather than by position. You see the same pattern in Course Schedule (graph as adjacency list) and in file system design problems. The dictionary lookup gives you O(1) access to any node's children, which keeps the birth operation fast.

2. Pre-order DFS with filtering

Walking a tree in pre-order while skipping certain nodes:

def dfs(name):
    if name not in dead:
        order.append(name)
    for child in children.get(name, []):
        dfs(child)

This is the standard pre-order traversal pattern with one addition: a filter condition before adding the node to the result. The structure is identical to Binary Tree Preorder Traversal, but generalized to N-ary trees (loop over all children instead of just left and right) and augmented with the dead-set check. The critical detail is that you always recurse into children regardless of whether the current node is dead. The filter only affects the output, not the traversal.

Edge cases

• No deaths: Everyone is alive. getInheritanceOrder returns the full pre-order traversal.
• King is dead: The king is skipped in the output, but DFS still starts from the king and visits all descendants.
• All dead: Every person has died. getInheritanceOrder returns an empty list. The DFS still runs through the whole tree but adds no one.
• Single person: Only the king exists with no children. The output is [kingName] (or empty if the king is dead).
• Deep chain: A long chain of single children (great-great-great-grandchildren). The recursion depth equals the chain length. Python's default recursion limit is 1000, which is sufficient for the problem's constraints (<= 10^5 calls), but if you are worried, you can convert the DFS to an iterative approach using a stack.
• Birth after death: A dead person can still have children born to them. Those children appear in the inheritance order at the correct position.

From understanding to recall

You have seen how the throne inheritance system works. The tree is stored as a hash map of children lists, deaths are tracked in a set, and the inheritance order is a pre-order DFS with dead-node filtering. Conceptually, none of this is complicated.

But in an interview, you need to write the __init__, birth, death, and getInheritanceOrder methods from scratch. You need to remember to use setdefault for safe dictionary access. You need to remember that the DFS always recurses into children even when the current node is dead. Those details are easy to forget under pressure.

Spaced repetition closes that gap. You practice writing the hash-map tree construction and the filtered pre-order DFS from memory at increasing intervals. After a few rounds, the pattern is automatic. You see a tree design problem and the code flows out without hesitation.

Related posts

• Binary Tree Preorder Traversal - The foundation for the DFS used in this problem. Master pre-order traversal on binary trees first, then generalizing to N-ary trees is simple.
• Serialize and Deserialize Binary Tree - Another tree design problem where pre-order DFS is the core algorithm. Shows how pre-order traversal captures tree structure.
• Design Add and Search Words - A design problem that combines a trie with DFS. Same pattern of "design a data structure, then traverse it."

CodeBricks breaks the throne inheritance problem into its hash-map tree construction and filtered pre-order DFS building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree design problem shows up in your interview, you do not hesitate. You just write it.