1443. Minimum Time to Collect All Apples in a Tree - Explanation

Problem Link

Description

You are given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend one second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices a[i] and b[i]. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]

Output: 8

Explanation: The path that takes minimum time to collect all apples is: 0 -> 1 -> 4 -> 1 -> 5 -> 1 -> 0 -> 2 -> 0.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]

Output: 6

Explanation: The path that takes minimum time to collect all apples is: 0 -> 2 -> 0 -> 1 -> 5 -> 1 -> 0.

Constraints:

• 1 <= n <= 100,000
• edges.length == n - 1
• edges[i].length == 2
• 0 <= a[i] < b[i] <= n - 1
• hasApple.length == n

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

Intuition

We start at node 0 and need to visit all nodes that have apples. The key observation is that if a subtree contains any apple (either at the child node itself or deeper in the subtree), we must traverse the edge to that child and back, costing 2 seconds. We use DFS to compute the time needed for each subtree. If a child has an apple or its subtree requires time (meaning there's an apple deeper), we add 2 plus the child's subtree time to our current total.

Algorithm

1. Build an adjacency list from the edges (undirected tree).
2. Run DFS from node 0 with parent tracking to avoid revisiting:
   • For each child (excluding parent):
     • Recursively compute childTime for that subtree.
     • If childTime > 0 or the child has an apple, add 2 + childTime to the current time.
   • Return the accumulated time for this subtree.
3. Return the result of dfs(0, -1).

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        adj = {i: [] for i in range(n)}
        for par, child in edges:
            adj[par].append(child)
            adj[child].append(par)

        def dfs(cur, par):
            time = 0
            for child in adj[cur]:
                if child == par:
                    continue
                childTime = dfs(child, cur)
                if childTime > 0 or hasApple[child]:
                    time += 2 + childTime
            return time

        return dfs(0, -1)

Time & Space Complexity

• Time complexity: $O(V + E)$
• Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.

---

2. Topological Sort (Kahn's Algorithm)

Intuition

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.

Algorithm

1. Build an adjacency list and track the degree (number of connections) for each node.
2. Initialize a queue with all leaf nodes (degree 1, excluding node 0).
3. 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] + 2 to time[neighbor].
     • If the neighbor becomes a leaf (degree 1) and isn't the root, add it to the queue.
4. Return time[0].

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]

Time & Space Complexity

• Time complexity: $O(V + E)$
• Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.