Throne Inheritance — LeetCode 1600 Python Solution
MediumTreeDepth-First SearchDesignHash Table
- Problem
- #1600
- Pattern
- Tree Traversal
- Reading time
- 5 min
- Source
- leetcode.com
The 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.
Example
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 curOrderPython solution
Python
class ThroneInheritance:
def __init__(self, kingName: str):
self.king = kingName
self.dead = set()
self.g = defaultdict(list)
def birth(self, parentName: str, childName: str) -> None:
self.g[parentName].append(childName)
def death(self, name: str) -> None:
self.dead.add(name)
def getInheritanceOrder(self) -> List[str]:
def dfs(x: str):
x not in self.dead and ans.append(x)
for y in self.g[x]:
dfs(y)
ans = []
dfs(self.king)
return ans
# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the number of nodes auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1600. Throne Inheritance is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1600. Throne Inheritance?
- LeetCode 1600. Throne Inheritance is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1600. Throne Inheritance?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1600. Throne Inheritance?
- The Python solution on this page uses O(n), where n is the number of nodes auxiliary space.
- What topics does LeetCode 1600. Throne Inheritance cover?
- LeetCode 1600. Throne Inheritance is tagged Tree, Depth-First Search, Design and Hash Table on LeetCode.