Throne Inheritance - Practice Coding Problems

Throne Inheritance - Problem

A kingdom consists of a king, his children, his grandchildren, and so on. Every once in a while, someone in the family dies or a child is born.

The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let's define the recursive function Successor(x, curOrder), which given a person x and the inheritance order so far, returns who should be the next person after x in the order of inheritance.

Successor(x, curOrder):

if x has no children or all of x's children are in curOrder: if x is the king return null, else return Successor(x's parent, curOrder)
else return x's oldest child who's not in curOrder

Implement the ThroneInheritance class:

ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.
void birth(string parentName, string childName) Indicates that parentName gave birth to childName.
void death(string name) Indicates the death of name. The death of the person doesn't affect the Successor function nor the current inheritance order. You can treat it as just marking the person as dead.
string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.

Input & Output

Example 1 — Basic Operations

$ Input: operations = [["ThroneInheritance", "king"], ["birth", "king", "andy"], ["birth", "king", "bob"], ["birth", "king", "catherine"], ["birth", "andy", "matthew"], ["birth", "bob", "alex"], ["birth", "bob", "asha"], ["getInheritanceOrder"], ["death", "bob"], ["getInheritanceOrder"]]

› Output: [null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]

💡 Note: Initially: king -> andy (matthew) -> bob (alex, asha) -> catherine. After bob dies, inheritance skips bob but includes his children.

Example 2 — King Dies

$ Input: operations = [["ThroneInheritance", "king"], ["birth", "king", "andy"], ["getInheritanceOrder"], ["death", "king"], ["getInheritanceOrder"]]

› Output: [null, null, ["king", "andy"], null, ["andy"]]

💡 Note: When king dies, andy becomes the first in inheritance order

Example 3 — Deep Family Tree

$ Input: operations = [["ThroneInheritance", "king"], ["birth", "king", "andy"], ["birth", "andy", "jack"], ["birth", "jack", "noah"], ["getInheritanceOrder"]]

› Output: [null, null, null, null, ["king", "andy", "jack", "noah"]]

💡 Note: Deep tree follows DFS: king -> andy -> jack -> noah

Constraints

1 ≤ kingName.length, parentName.length, childName.length, name.length ≤ 15
kingName, parentName, childName, and name consist of lowercase English letters only.
All arguments kingName, parentName, childName, and name are distinct.
All name arguments of death will be passed to either ThroneInheritance constructor or as childName to birth first.
For each call to birth(parentName, childName), it is guaranteed that parentName is alive.
At most 10⁵ calls will be made to birth and death.
At most 10 calls will be made to getInheritanceOrder.

Visualization

Tap to expand

Understanding the Visualization

Family Tree

Build tree structure with parent-child relationships

Track Deaths

Mark deceased members without removing from tree

DFS Inheritance

Traverse tree depth-first, skip dead people

Key Takeaway

🎯 Key Insight: The inheritance order is simply a DFS traversal of the family tree, skipping deceased members

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that inheritance order follows a depth-first search (DFS) traversal of the family tree. Best approach uses a tree structure with adjacency lists for children and a separate set to track deaths. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Reconstruction	O(n)	O(n)	Rebuild the entire family tree and inheritance order for each query
DFS Tree Traversal	O(n)	O(n)	Use tree structure with DFS traversal to get inheritance order

Brute Force Reconstruction — Algorithm Steps

Store all operations in a list
For each getInheritanceOrder call, rebuild tree from scratch
Perform DFS to get inheritance order

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Operations

Keep track of all births and deaths

Rebuild Tree

Reconstruct family tree from operations

DFS Traversal

Perform depth-first search to get inheritance order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_PEOPLE 1000
#define MAX_NAME_LEN 50

typedef struct {
    char king[MAX_NAME_LEN];
    char children[MAX_PEOPLE][MAX_PEOPLE][MAX_NAME_LEN];
    int childCount[MAX_PEOPLE];
    int dead[MAX_PEOPLE];
    char names[MAX_PEOPLE][MAX_NAME_LEN];
    int nameCount;
} ThroneInheritance;

int findPerson(ThroneInheritance* t, const char* name) {
    for (int i = 0; i < t->nameCount; i++) {
        if (strcmp(t->names[i], name) == 0) {
            return i;
        }
    }
    strcpy(t->names[t->nameCount], name);
    return t->nameCount++;
}

void birth(ThroneInheritance* t, const char* parent, const char* child) {
    int parentId = findPerson(t, parent);
    int childId = findPerson(t, child);
    strcpy(t->children[parentId][t->childCount[parentId]++], child);
}

void death(ThroneInheritance* t, const char* name) {
    int id = findPerson(t, name);
    t->dead[id] = 1;
}

void dfs(ThroneInheritance* t, const char* person, char result[][MAX_NAME_LEN], int* count) {
    int id = findPerson(t, person);
    if (!t->dead[id]) {
        strcpy(result[(*count)++], person);
    }
    for (int i = 0; i < t->childCount[id]; i++) {
        dfs(t, t->children[id][i], result, count);
    }
}

char** solution(char*** operations, int opCount) {
    return NULL;
}

int main() {
    printf("[null,[\"king\"]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each operation takes O(n) time due to tree reconstruction

✓ Linear Growth

Space Complexity

O(n)

Store all family members and their relationships

⚡ Linearithmic Space

31.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Reconstruction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler