Prerequisites :- DFS
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1. Some of the nodes have gold coins in them. It takes 1 minute to walk over one edge of the tree. Determine the minimum time in minutes you have to spend to collect all coins in the tree, starting at root node 1 and coming back to it.
Solution Approach:
The solution uses a depth-first search to traverse the tree, keeping track of the time spent to collect all the coins.
Let’s break down the algorithm step by step:
DFS Function:
-
The DFS function recursively visits each node and has a boolean array indicating whether each vertex has a coin.
-
It initializes a variable ans to 0, representing the time spent at the current node.
-
Traversal of Children:
- The DFS function is called recursively on that child to get the coins from the children
-
Time Calculation:
- The result (res) from the recursive call represents the time spent at the child node and its subtree.
- If res is greater than 0 or the current child has a coin, it adds (res + 2) to ans. The additional 2 seconds account for 1 second to go to the child and 1 second to return.
-
Return Result:
- The function returns the total time spent (ans) at the current node and its subtree.
Time Complexity: O(N + E) = O(N), where N is the number of nodes and E is the no. of edges in the tree. This runtime is due to the dfs traversal.
Space Complexity: O(1), as the algorithm doesn’t use extra space.