easyTreesPattern: DFS
Tree Node Resource Sum Solution
Problem Statement
You are given a tree structure represented by an adjacency list where keys are parent nodes and values are lists of their direct children. You are also given a mapping of node IDs to their initial resource values. Calculate the total accumulated resource value for each node in the tree. The accumulated value for a node is its initial resource value plus the sum of accumulated resource values of all its children. Return a map where keys are node IDs and values are their total accumulated resource values.
Examples
Example 1:
Input:{"adj":{"0":["1","2"],"1":["3"],"2":[],"3":[]},"resources":{"0":10,"1":5,"2":8,"3":3}}
Output:{"0":26,"1":8,"2":8,"3":3}
Explanation: Node 3 has an initial resource of 3. Node 1 has an initial resource of 5 plus its child's accumulated resource (3), so 5 + 3 = 8. Node 2 has an initial resource of 8 and no children, so its accumulated resource is 8. Node 0 has an initial resource of 10 plus the accumulated resources of its children (8 + 8), so 10 + 8 + 8 = 26.
Example 2:
Input:{"adj":{"a":["b","c"],"b":["d"],"c":[],"d":[]},"resources":{"a":100,"b":50,"c":75,"d":25}}
Output:{"a":250,"b":75,"c":75,"d":25}
Explanation: Node d: 25. Node b: 50 + 25 = 75. Node c: 75. Node a: 100 + 75 + 75 = 250.
Example 3:
Input:{"adj":{"root":[]},"resources":{"root":50}}
Output:{"root":50}
Explanation: A single node tree. The root node has an initial resource of 50 and no children, so its total accumulated resource is 50.
Constraints
- The number of nodes in the tree can range from 1 to 1000.
- Node IDs are unique strings or integers.
- Resource values are non-negative integers.
- The input adjacency list represents a valid tree structure (no cycles, exactly one root if not explicitly given, though the problem does not require identifying a root).
- All nodes mentioned in the adjacency list values exist as keys in the adjacency list or have associated resources.
Time: O(N + E) Space: O(N)
Use a Depth First Search (DFS) starting from any node that has no incoming edges (a root, though any node can initiate the traversal if you handle visited nodes correctly or assume a forest structure where you might need to start DFS from all nodes without parents). The DFS function should recursively calculate the total resource for its children. Upon returning from child calls, it sums their results with its own initial resource, stores the total for the current node, and returns this total to its parent. This ensures each node's resource is calculated exactly once.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import Dict, List
def tree_node_resource_sum(adj: Dict[str, List[str]], resources: Dict[str, int]) -> Dict[str, int]:
total_resources = {}
def dfs(node):
if node in total_resources:
return total_resources[node]
current_total = resources.get(node, 0)
children = adj.get(node, [])
for child in children:
current_total += dfs(child)
total_resources[node] = current_total
return current_total
# We need to find the root(s) of the tree(s).
# A node is a root if it's a key in adj but not a value in any adj list.
all_nodes = set(adj.keys()).union(set(resources.keys()))
child_nodes = set()
for children_list in adj.values():
child_nodes.update(children_list)
roots = all_nodes - child_nodes
# If there are no explicit roots (e.g., empty adj/resources, or a single node with no children)
# then we should iterate through all nodes that have resources defined and start DFS from them.
if not roots:
for node_id in resources:
dfs(node_id)
else:
for root in roots:
dfs(root)
# Ensure all nodes that have resources are accounted for, even if they are isolated or part of a disconnected graph.
for node_id in resources:
if node_id not in total_resources:
dfs(node_id)
return total_resources