LeetCode 1600 - Throne Inheritance

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Design

Solution

Problem Understanding

The problem asks us to design a data structure that simulates a royal inheritance system. There is a king at the top of the family tree, and over time people can be born or die. We must support three operations efficiently:

Add a child to an existing person.
Mark a person as dead.
Return the current inheritance order.

The inheritance order follows a preorder traversal of the family tree. A parent always appears before their children, and among siblings, older children appear before younger children. Since births are added chronologically, the order in which children are inserted matters.

An important detail is that death does not remove a person from the family tree. Dead people still affect traversal order because their descendants must remain in the correct position. The only difference is that dead people are skipped when producing the final inheritance list.

The recursive Successor definition in the statement effectively describes a preorder depth first traversal:

Visit the current person.
Recursively visit each child from oldest to youngest.

The input operations dynamically modify the family tree. The birth operation adds a directed parent to child relationship. The death operation simply marks a person as dead. The getInheritanceOrder operation must return all living people in the correct inheritance order.

The constraints are very important:

Up to 10^5 calls can be made to birth and death.
Only up to 10 calls are made to getInheritanceOrder.

This tells us that updates happen much more frequently than queries. That observation strongly influences the design choice. We do not want to rebuild expensive structures after every birth or death. Instead, we should store the family tree incrementally and generate the inheritance order only when requested.

Several edge cases are important:

The king may die, but their descendants still inherit in the same order.
A dead person's children must still appear in the inheritance list.
A person may have many children, and birth order must remain preserved.
The inheritance order query may happen after many updates.
The tree can become very deep, so recursive traversal should still remain correct within practical limits.

Approaches

Brute Force Approach

A brute force approach would attempt to explicitly maintain the inheritance order after every operation.

For example, after every birth or death, we could rebuild the entire inheritance sequence by simulating the Successor process from scratch. This would involve traversing the whole family tree repeatedly.

The approach is correct because preorder traversal naturally matches the inheritance rules. However, rebuilding the entire order after every update is expensive.

If there are N people and we rebuild the order after every operation, the total cost can become O(N^2) across many operations.

Since there can be up to 10^5 updates, repeatedly recomputing the entire order is inefficient.

Optimal Approach

The key insight is that births and deaths only modify local information:

Birth adds a child to a parent's children list.
Death marks a person as deceased.

Neither operation requires recomputing the inheritance order immediately.

Because getInheritanceOrder is called at most 10 times, we can defer all expensive work until query time. We store:

An adjacency list representing the family tree.
A set containing dead people.
The king's name.

When getInheritanceOrder is called, we perform a preorder DFS traversal:

Visit the current person.
Add them to the result if alive.
Recursively process children in birth order.

This directly mirrors the inheritance rules.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N) per update	O(N)	Rebuilds inheritance order repeatedly
Optimal	Birth: O(1), Death: O(1), Query: O(N)	O(N)	Stores tree and computes order only when needed

Algorithm Walkthrough

Optimal Algorithm

Initialize the data structure with the king's name.

We store the king separately because traversal always starts from the king. We also create:

A hash map from parent to list of children.
A set of dead people.

Handle births by appending the child to the parent's child list.

The order of insertion matters because inheritance follows oldest to youngest child order. Appending naturally preserves this ordering. 3. Handle deaths by adding the person's name to the dead set.

We do not remove them from the tree because their descendants still inherit in the same location. 4. When getInheritanceOrder is called, start a preorder DFS from the king.

The traversal follows the inheritance rules exactly:

Process the current person first.
Then recursively process children from oldest to youngest.

During DFS, add only living people to the result.

Dead people are skipped, but traversal continues through their descendants. 6. Return the completed result list.

Why it works

The inheritance rules are equivalent to preorder traversal of the family tree. Every parent appears before descendants, and siblings are visited in birth order. Since births append children in chronological order, the DFS traversal naturally produces the correct inheritance sequence. Skipping dead people while continuing traversal preserves the required ordering of descendants.

Python Solution

from collections import defaultdict
from typing import List

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.children = defaultdict(list)
        self.dead = set()

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

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

    def getInheritanceOrder(self) -> List[str]:
        order = []

        def dfs(person: str) -> None:
            if person not in self.dead:
                order.append(person)

            for child in self.children[person]:
                dfs(child)

        dfs(self.king)
        return order

The implementation stores the royal family as a tree using an adjacency list. The children dictionary maps each person to their list of children in birth order.

The constructor initializes the king, the adjacency list, and the dead set.

The birth method appends the child to the parent's child list. Since births occur chronologically, appending preserves oldest to youngest ordering automatically.

The death method adds the person to the dead set. We intentionally keep dead people in the tree because their descendants still belong in the inheritance order.

The getInheritanceOrder method performs a preorder DFS traversal. If the current person is alive, they are added to the result. Then all children are recursively processed in order.

This implementation directly mirrors the inheritance definition from the problem statement.

Go Solution

package main

type ThroneInheritance struct {
	king     string
	children map[string][]string
	dead     map[string]bool
}

func Constructor(kingName string) ThroneInheritance {
	return ThroneInheritance{
		king:     kingName,
		children: make(map[string][]string),
		dead:     make(map[string]bool),
	}
}

func (this *ThroneInheritance) Birth(parentName string, childName string) {
	this.children[parentName] = append(this.children[parentName], childName)
}

func (this *ThroneInheritance) Death(name string) {
	this.dead[name] = true
}

func (this *ThroneInheritance) GetInheritanceOrder() []string {
	order := []string{}

	var dfs func(string)

	dfs = func(person string) {
		if !this.dead[person] {
			order = append(order, person)
		}

		for _, child := range this.children[person] {
			dfs(child)
		}
	}

	dfs(this.king)

	return order
}

The Go implementation follows the same logic as the Python version.

The children structure uses a map from string to slice of strings. Slices naturally preserve insertion order, which is important for maintaining birth order.

The dead structure is implemented as a map[string]bool because Go does not have a built in set type.

The DFS traversal is implemented using a nested function closure. The recursion appends living people to the result slice while continuing traversal through all descendants.

Worked Examples

Example 1

Input:

["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]

Step by Step State

Operation	Children Map	Dead Set
Initialize king	`{}`	`{}`
birth("king", "andy")	`king -> [andy]`	`{}`
birth("king", "bob")	`king -> [andy, bob]`	`{}`
birth("king", "catherine")	`king -> [andy, bob, catherine]`	`{}`
birth("andy", "matthew")	`andy -> [matthew]`	`{}`
birth("bob", "alex")	`bob -> [alex]`	`{}`
birth("bob", "asha")	`bob -> [alex, asha]`	`{}`

Now we call getInheritanceOrder().

DFS Traversal

Current Person	Alive?	Current Result
king	Yes	[king]
andy	Yes	[king, andy]
matthew	Yes	[king, andy, matthew]
bob	Yes	[king, andy, matthew, bob]
alex	Yes	[king, andy, matthew, bob, alex]
asha	Yes	[king, andy, matthew, bob, alex, asha]
catherine	Yes	[king, andy, matthew, bob, alex, asha, catherine]

Returned result:

["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]

Now death("bob") is called.

Operation	Dead Set
death("bob")	`{bob}`

Call getInheritanceOrder() again.

DFS Traversal After Death

Current Person	Alive?	Current Result
king	Yes	[king]
andy	Yes	[king, andy]
matthew	Yes	[king, andy, matthew]
bob	No	[king, andy, matthew]
alex	Yes	[king, andy, matthew, alex]
asha	Yes	[king, andy, matthew, alex, asha]
catherine	Yes	[king, andy, matthew, alex, asha, catherine]

Returned result:

["king", "andy", "matthew", "alex", "asha", "catherine"]

Complexity Analysis

Measure	Complexity	Explanation
Time	Birth: O(1), Death: O(1), GetInheritanceOrder: O(N)	DFS visits every person once
Space	O(N)	Stores family tree and dead set

The birth operation is constant time because appending to a child list is O(1) amortized. The death operation is also constant time because hash set insertion is O(1) average case.

The getInheritanceOrder operation performs a preorder traversal over the entire family tree. Every person is visited exactly once, so the complexity is O(N).

The space complexity is O(N) because we store all people in the adjacency list and possibly in the dead set.

Test Cases

from typing import List
from collections import defaultdict

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.children = defaultdict(list)
        self.dead = set()

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

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

    def getInheritanceOrder(self) -> List[str]:
        result = []

        def dfs(person: str):
            if person not in self.dead:
                result.append(person)

            for child in self.children[person]:
                dfs(child)

        dfs(self.king)

        return result

# Example from problem statement
t = ThroneInheritance("king")
t.birth("king", "andy")
t.birth("king", "bob")
t.birth("king", "catherine")
t.birth("andy", "matthew")
t.birth("bob", "alex")
t.birth("bob", "asha")

assert t.getInheritanceOrder() == [
    "king",
    "andy",
    "matthew",
    "bob",
    "alex",
    "asha",
    "catherine"
]  # standard preorder inheritance

t.death("bob")

assert t.getInheritanceOrder() == [
    "king",
    "andy",
    "matthew",
    "alex",
    "asha",
    "catherine"
]  # dead person removed but descendants preserved

# Only king exists
t2 = ThroneInheritance("king")

assert t2.getInheritanceOrder() == ["king"]  # minimal case

# King dies
t3 = ThroneInheritance("king")
t3.birth("king", "a")
t3.birth("a", "b")
t3.death("king")

assert t3.getInheritanceOrder() == ["a", "b"]  # dead king excluded

# Deep inheritance chain
t4 = ThroneInheritance("k")
t4.birth("k", "a")
t4.birth("a", "b")
t4.birth("b", "c")
t4.birth("c", "d")

assert t4.getInheritanceOrder() == [
    "k", "a", "b", "c", "d"
]  # deep DFS traversal

# Dead person with living descendants
t5 = ThroneInheritance("k")
t5.birth("k", "a")
t5.birth("a", "b")
t5.birth("b", "c")

t5.death("a")

assert t5.getInheritanceOrder() == [
    "k", "b", "c"
]  # descendants still appear

# Multiple siblings preserve birth order
t6 = ThroneInheritance("k")
t6.birth("k", "a")
t6.birth("k", "b")
t6.birth("k", "c")

assert t6.getInheritanceOrder() == [
    "k", "a", "b", "c"
]  # sibling order preserved

# Multiple deaths
t7 = ThroneInheritance("k")
t7.birth("k", "a")
t7.birth("k", "b")
t7.birth("a", "c")

t7.death("a")
t7.death("b")

assert t7.getInheritanceOrder() == [
    "k", "c"
]  # multiple dead nodes skipped

Test	Why
Problem statement example	Validates standard preorder inheritance
Only king exists	Tests smallest possible tree
King dies	Ensures dead root is skipped correctly
Deep inheritance chain	Verifies recursive DFS traversal
Dead person with descendants	Confirms descendants remain reachable
Multiple siblings	Ensures birth order preservation
Multiple deaths	Tests skipping several dead people

Edge Cases

The king dies

One subtle case is when the king is marked as dead. A naive implementation might incorrectly remove the entire subtree rooted at the king. That would be wrong because descendants still inherit.

This implementation handles the case correctly because death only adds the king to the dead set. During DFS traversal, the king is skipped in the output, but traversal still continues through all descendants.

A dead person has living children

Another important edge case occurs when someone dies after having children. Their descendants must still appear in the inheritance order exactly where they normally would.

The DFS traversal naturally handles this. The dead person is skipped when building the result list, but recursion still processes all children. This preserves the inheritance structure correctly.

Large number of birth operations

With up to 10^5 operations, repeatedly recomputing inheritance order after every birth would be too slow.

This implementation avoids that issue by storing births incrementally in an adjacency list. Each birth only appends to a list in constant time. Expensive traversal is deferred until getInheritanceOrder is actually requested, which happens at most 10 times.