# TREECOINS - Editorial

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.