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.