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).
This approach uses a DFS traversal to determine the minimal path needed to return to the starting node after collecting all coins. It calculates the number of edges that need to be traversed with consideration of reachable coins at each step. The DFS explores each node and checks its adjacent nodes for coin presence alongside setting an optimal route back.
The C solution implements a DFS function to traverse the graph. The configuration uses adjacency lists to represent the edges of the tree. By invoking dfs(), it calculates the total number of unique paths required to collect all coins and return to the starting node. The function collectCoins() sums two times the DFS result minus one, owing to counting each edge twice on the return trip.
Time Complexity: O(n) due to the DFS traversal visiting all nodes once.
Space Complexity: O(n) for the adjacency list representation and visited array.
This approach involves using the Breadth-First Search (BFS) method with a queue to dynamically explore the tree in slices of depth-limited exploration. It records each potential realization of coin acquisition using a range-bound periphery, leveraging spatial layers to evaluate all reachable nodes distinctly within optimal edge traversal focus.
The BFS solution in C utilizes an adjacency matrix to represent connections between nodes after initializing levels and visiting indices. The breadth-first circuit run systematically identifies reachability and collates edge quantity necessary for traversing given coin presence.
Time Complexity: O(n^2) due to the adjacency matrix and bilinear node checks.
Space Complexity: O(n^2) in maintaining matrix overhead structure.
We first convert the edges in edges to the adjacency list g, where g[i] represents all the adjacent nodes of node i, represented by a set.
Then we traverse all nodes and find the nodes where coins[i]=0 and g[i] only has one node (that is, the leaf node where the coin is 0), and add them to the queue q.
Then we continuously remove nodes from the queue and delete them from the adjacent list. Then we check whether the adjacent nodes meet the condition where coins[j]=0 and g[j] only has one node. If it meets, we add it to the queue q. Loop until the queue is empty.
After the above operation, we get a new tree, and the leaf nodes of the tree are all nodes where the coin is 1.
Then, we delete the remaining two layers of leaf nodes, and finally get a tree where all nodes need to be visited. We only need to count the number of edges and multiply it by 2 to get the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Approach | Time Complexity: O(n) due to the DFS traversal visiting all nodes once. |
| BFS and Queue-Based Approach | Time Complexity: O(n^2) due to the adjacency matrix and bilinear node checks. |
| Topological sorting | — |
| 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. |
Collect Coins in a Tree | In Out DP Explained | Weekly Contest 338 • codingMohan • 4,615 views views
Watch 5 more video solutions →Practice Collect Coins in a Tree with our built-in code editor and test cases.
Practice on FleetCode