Design Tree Operations with DFS and BFS

Hierarchical Cluster Resource Explorer

In distributed infrastructure management, compute resources are often organized hierarchically (e.g., Region -> Datacenter -> Rack -> Host -> Accelerators). You are asked to implement a class ClusterManager that operates on an N-ary tree of compute resources.

Each node in the tree is defined as:

class ResourceNode:
    def __init__(self, node_id: str, capacity: int, children: list = None):
        self.node_id = node_id
        self.capacity = capacity
        self.children = children if children is not None else []

Implement the following methods in ClusterManager:

1. find_shallowest_with_capacity(min_capacity: int) -> str | None Uses BFS to find the ID of the node closest to the root that has capacity >= min_capacity. If multiple qualifying nodes exist at the same depth, return the one visited first (left-to-right based on children order). If no such node exists, return None.

2. max_capacity_path() -> list[str] Uses DFS to find the path from the root to any leaf node that yields the maximum cumulative capacity (sum of capacity along the path). Return the path as a list of node IDs. If multiple paths have the same maximum sum, return the leftmost path.

3. level_capacity_totals() -> list[int] Uses BFS to return a list of integers where the i-th element represents the sum of capacities of all nodes at depth i (with the root at depth 0).

Examples

Example 1

# Tree structure:
#          root (cap: 10)
#         /              \
#    rack-1 (cap: 20)    rack-2 (cap: 5)
#      /         \             \
# host-1 (cap: 30) host-2 (cap: 15) host-3 (cap: 50)

root = ResourceNode("root", 10, [
    ResourceNode("rack-1", 20, [
        ResourceNode("host-1", 30),
        ResourceNode("host-2", 15)
    ]),
    ResourceNode("rack-2", 5, [
        ResourceNode("host-3", 50)
    ])
])

manager = ClusterManager(root)

manager.find_shallowest_with_capacity(20)
# Output: "rack-1"
# Explanation: "rack-1" is at depth 1 with capacity 20 >= 20. "host-3" has 50 but is at depth 2.

manager.max_capacity_path()
# Output: ["root", "rack-2", "host-3"]
# Explanation: 
# Path 1: 10 + 20 + 30 = 60
# Path 2: 10 + 20 + 15 = 45
# Path 3: 10 + 5 + 50 = 65 -> Maximum

manager.level_capacity_totals()
# Output: [10, 25, 95]
# Explanation: Depth 0: 10; Depth 1: 20 + 5 = 25; Depth 2: 30 + 15 + 50 = 95.

Constraints

• The tree contains N nodes where 1 <= N <= 20,000.
• 0 <= capacity <= 10^6 for each node.
• Node IDs are non-empty unique strings.
• Tree depth will not exceed 2,000.

Edge Cases

• Single node tree (root has no children).
• All nodes have capacity strictly less than min_capacity.
• Deep linear chains (ensure DFS does not hit stack overflow or uses iteration).