Prerequisites :- DFS
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1, find the subtree sum of each node i. (Note: Subtree of any node i contains all nodes which are descendants of it including node i)
Solution Approach:
The problem can be solved using the Depth-First Search (DFS) traversal, which helps in computing the subtree sum for each node.
1. Maintain an array to store the cumulative sum of nodes in each subtree.
2. Call the DFS function from the root node (node 1).
3. During the traversal, calculate the subtree sum for each node, including itself and its children.
4. Subtree Sum Calculation:
4a: For each node, add its own value to the subtree sum.
4b: For each child of the current node, recursively call the DFS function.
4c: Update the subtree sum of the current node by adding the subtree sums of its
children.
Time Complexity: O(N + E) = O(N) as E = N - 1 in case of trees, where N is the number of nodes, E is no. of edges in the tree. The DFS traversal visits each node and edge once.
Space Complexity: O(N), as the algorithm utilizes an array to store subtree sums for each node.