Is Minimum Time to Collect All Apples in a Tree easy or hard?

The problem is classified as Medium because it requires recognizing a tree traversal pattern and implementing conditional cost accumulation. The DFS logic is straightforward once you realize that only subtrees containing apples should contribute to the total traversal time.

Minimum Time to Collect All Apples in a Tree Python/Java solution

In Python or Java, build an adjacency list from the edges and run a DFS starting at node 0. Each recursive call returns the time needed for its subtree. If a child subtree requires time or contains an apple, add 2 seconds to include that edge in the traversal. The total aggregated value is the answer.

How to solve Minimum Time to Collect All Apples in a Tree in O(n)?

Construct an adjacency list for the tree and perform a DFS from node 0. For each child subtree, recursively compute the time required to collect apples. If the subtree contains an apple or requires traversal time, add 2 seconds for the round trip along that edge. Summing these costs across relevant subtrees gives the minimum time.

What is the best approach for Minimum Time to Collect All Apples in a Tree?

DFS traversal with backtracking is the most efficient and commonly expected approach. Starting from the root, recursively explore each subtree and only add traversal cost if the subtree contains at least one apple. This ensures unnecessary branches are skipped and each node is processed once, resulting in O(n) time complexity.

Is Minimum Time to Collect All Apples in a Tree asked at Google/Amazon/Meta?

Tree traversal problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests DFS reasoning, graph representation with adjacency lists, and the ability to aggregate results from subtrees efficiently.

What data structure is used in Minimum Time to Collect All Apples in a Tree?

The solution primarily uses an adjacency list to represent the tree graph. DFS recursion or a stack processes nodes, while arrays or lists track whether each node contains an apple. In alternative strategies, BFS queues and parent maps may also be used.

What is the time complexity of Minimum Time to Collect All Apples in a Tree?

The optimal solution runs in O(n) time because each node and edge in the tree is visited once during traversal. Building the adjacency list also takes O(n). Space complexity is O(n) due to the adjacency list and recursion stack used in DFS.

Description Hints 2 Solution Video 12:25

1443. Minimum Time to Collect All Apples in a Tree

Medium63.6% acceptance4 companies

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 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] = [a_i, b_i] 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 figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

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 figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 3:

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

Constraints:

1 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i < b_i <= n - 1
hasApple.length == n

Asked at 4 companies

Cisco Meta Microsoft Amazon

Topics

Hints open one at a time

Hint 1

Note that if a node u contains an apple then all edges in the path from the root to the node u have to be used forward and backward (2 times).

Hint 2

Therefore use a depth-first search (DFS) to check if an edge will be used or not.

12:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

7
[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]
[false,false,true,false,true,true,false]

Input

7
[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]
[false,false,true,false,false,true,false]

Input

7
[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]
[false,false,false,false,false,false,false]

Your code is saved on this device.Solution