Minimum Time to Collect All Apples in a Tree
Medium · Graphs · Explanation and code example
Topological Sort (Kahn's Algorithm)
How it works
Instead of top-down DFS, we can process the tree from leaves to root. Starting from leaf nodes (nodes with only one connection, excluding the root), we propagate the time upward. If a leaf has an apple or already accumulated time from its subtree, we add 2 seconds to its parent. This bottom-up approach naturally handles the aggregation of times from multiple subtrees.
Steps
- Build an adjacency list and track the degree (number of connections) for each node.
- Initialize a queue with all leaf nodes (degree
1, excluding node0). - Process nodes in the queue:
- For each neighbor of the current node with positive degree:
- Decrement the neighbor's degree.
- If the current node has an apple or has accumulated time, add
time[node] + 2totime[neighbor]. - If the neighbor becomes a leaf (degree
1) and isn't the root, add it to the queue.
- For each neighbor of the current node with positive degree:
- Return
time[0].
Complexity
- Time complexity:
O(V + E) - Space complexity:
O(V + E)
Where
Vis the number of vertices andEis the number of edges.
Things to watch for
Not Tracking Parent Nodes
Since the tree is given as an undirected edge list, each edge appears in both directions in the adjacency list. Without tracking the parent node during DFS, you will revisit the parent as if it were a child, causing infinite recursion or incorrect double-counting of edges. Always pass the parent node to recursive calls and skip it when iterating through neighbors.
Counting Edges Instead of Round Trips
Each edge must be traversed twice (once going down to collect apples, once coming back up). A common mistake is adding 1 instead of 2 to the time when an edge needs to be traversed. This results in answers that are exactly half of the correct value.
Ignoring Apples in Subtrees
Some solutions only check if the current child node has an apple, forgetting that we also need to traverse to a child if its subtree contains apples deeper down. The correct condition is: traverse to a child if hasApple[child] is true OR if childTime > 0 (meaning the subtree required time, indicating apples exist deeper).
Python code example
from typing import List
from collections import defaultdict, deque
class Solution:
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
adj = defaultdict(list)
indegree = [0] * n
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
indegree[u] += 1
indegree[v] += 1
queue = deque()
for i in range(1, n):
if indegree[i] == 1:
queue.append(i)
indegree[i] = 0
time = [0] * n
while queue:
node = queue.popleft()
for nei in adj[node]:
if indegree[nei] <= 0:
continue
indegree[nei] -= 1
if hasApple[node] or time[node] > 0:
time[nei] += time[node] + 2
if indegree[nei] == 1 and nei != 0:
queue.append(nei)
return time[0]
C++ code example
class Solution {
public:
int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
vector<vector<int>> adj(n);
vector<int> indegree(n, 0);
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
indegree[edge[0]]++;
indegree[edge[1]]++;
}
queue<int> q;
for (int i = 1; i < n; ++i) {
if (indegree[i] == 1) {
q.push(i);
indegree[i] = 0;
}
}
vector<int> time(n, 0);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (indegree[neighbor] <= 0) {
continue;
}
indegree[neighbor]--;
if (hasApple[node] || time[node] > 0) {
time[neighbor] += time[node] + 2;
}
if (indegree[neighbor] == 1 && neighbor != 0) {
q.push(neighbor);
}
}
}
return time[0];
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.