Watch 6 video solutions for Collect Coins in a Tree, a hard level problem involving Array, Tree, Graph. This walkthrough by codingMohan has 4,615 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given an integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an array coins of size n where coins[i] can be either 0 or 1, where 1 indicates the presence of a coin in the vertex i.
Initially, you choose to start at any vertex in the tree. Then, you can perform the following operations any number of times:
2 from the current vertex, orFind the minimum number of edges you need to go through to collect all the coins and go back to the initial vertex.
Note that if you pass an edge several times, you need to count it into the answer several times.
Example 1:
Input: coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]] Output: 2 Explanation: Start at vertex 2, collect the coin at vertex 0, move to vertex 3, collect the coin at vertex 5 then move back to vertex 2.
Example 2:
Input: coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]] Output: 2 Explanation: Start at vertex 0, collect the coins at vertices 4 and 3, move to vertex 2, collect the coin at vertex 7, then move back to vertex 0.
Constraints:
n == coins.length1 <= n <= 3 * 1040 <= coins[i] <= 1edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges represents a valid tree.Problem Overview: You are given a tree with n nodes where some nodes contain coins. Starting from any node, you can collect coins within distance 2 without visiting every node directly. The goal is to compute the minimum number of edge traversals required to collect all coins and return to the start.
Approach 1: Depth-First Search (DFS) Pruning (O(n) time, O(n) space)
This approach treats the tree as a graph and performs a post-order DFS. Build an adjacency list and recursively process children while tracking whether a subtree contains coins. If a subtree has no coins, its edges can be ignored entirely because visiting it contributes nothing to the final answer. When a subtree contains coins, you add the cost of traversing the edge to that subtree and back (two traversals). The key insight: only edges that lead to coin-containing subtrees matter. DFS propagates coin presence upward so the algorithm prunes unnecessary branches early.
During recursion, maintain a visited set to avoid revisiting parent nodes. Each DFS call returns whether the current subtree has coins and the traversal cost accumulated so far. This approach directly models the idea that useless leaf paths should be removed from the traversal tree.
Approach 2: BFS and Queue-Based Graph Pruning (Topological Sort) (O(n) time, O(n) space)
The optimal approach repeatedly removes useless leaves using a queue. First construct adjacency lists and compute node degrees. Push all leaf nodes without coins into a queue and iteratively remove them. Each removal decreases the degree of its neighbor. This step prunes entire branches that never contribute coins.
After pruning zero-coin leaves, perform two additional rounds of leaf removal. Coins can be collected from nodes within distance two, so the outer two layers of the remaining tree never need to be traversed. Using a queue and degree tracking, remove these layers similar to topological sort. What remains are the edges that must actually be traversed.
The final answer is twice the number of remaining edges because each edge must be walked forward and back. This approach works because tree pruning gradually reveals the minimal subgraph that still contains all coins beyond the free collection radius.
Recommended for interviews: The BFS pruning approach is what most interviewers expect. It shows strong understanding of tree structure, degree tracking, and graph trimming. Starting with the DFS reasoning helps demonstrate intuition about ignoring empty subtrees, but the queue-based pruning solution is cleaner and easier to reason about in O(n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) Pruning | O(n) | O(n) | Useful when reasoning recursively about subtree coin presence and pruning empty branches. |
| BFS Leaf Pruning (Topological Sort) | O(n) | O(n) | Best general solution. Efficiently trims unnecessary leaves and computes minimal traversal edges. |