Skip to main content
Talentd

Minimum Time to Collect All Apples in a Tree - Solution & Explanation

MediumHash TableTreeDepth-First SearchBreadth-First Search14 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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] = [ai, bi] means that exists an edge connecting the vertices ai and bi. 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 <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai < bi <= n - 1
  • hasApple.length == n

Approach Overview

Problem Overview: You are given an undirected tree with n nodes where some nodes contain apples. Starting from node 0, you must collect every apple and return to the root. Each edge traversal costs 1 second. The goal is to compute the minimum time needed to visit all apple nodes and return.

Approach 1: DFS Traversal with Backtracking (O(n) time, O(n) space)

The tree structure naturally fits a depth-first traversal. Build an adjacency list for the graph, then run DFS from node 0. Each recursive call explores child nodes while skipping the parent to avoid revisiting edges. The key insight: only add traversal cost if a subtree contains an apple. If a child subtree returns a positive cost or the child node itself has an apple, you add 2 seconds to account for traveling to that child and returning. Otherwise, skip that branch entirely. This selective accumulation ensures you only traverse edges that lead to apples. DFS works well because it aggregates information bottom‑up: each subtree reports whether collecting apples below it required travel.

This approach relies heavily on tree traversal and recursive aggregation, a common pattern in problems involving subtree properties. You process each node once, so time complexity stays linear.

Approach 2: BFS Alternative Strategy (O(n) time, O(n) space)

A breadth-first strategy can solve the problem by first building parent relationships from the root using BFS. After constructing the parent map, iterate through all nodes that contain apples and trace the path back to the root. Mark edges that must be used to reach these apples. A set or boolean structure tracks visited edges so shared paths are counted only once. Each unique edge required for collecting apples contributes 2 seconds because you travel down and back along that edge.

This method uses breadth-first search for tree exploration and leverages parent pointers to reconstruct paths efficiently. Compared to DFS, it separates graph traversal from cost calculation. The logic is sometimes easier to visualize but requires additional structures to track visited edges.

Recommended for interviews: DFS with backtracking is the expected solution. Interviewers want to see you recognize that the graph is a tree and that only subtrees containing apples should contribute to the traversal cost. The bottom‑up aggregation pattern is common in depth-first search tree problems. BFS works but adds unnecessary bookkeeping, while DFS expresses the logic more directly.

Approach 1: DFS Traversal with Backtracking

This approach involves using Depth-First Search (DFS) to traverse the tree from the root node (vertex 0). We recursively explore each subtree from the current node. If a subtree contains any apples, we add the cost of traversing to and from that subtree (2 units of time per edge, as we have to go there and come back). This ensures that the solution captures only the necessary paths contributing to the apple collection.

The C solution implements the DFS traversal with a recursive function. An adjacency list represents the graph, and we use it to explore each node's children. We check if a child (subtree) has apples; if so, we add 2 to the total time, accounting for both the forward and return traversal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of vertices. We explore each vertex once in the DFS traversal.
Space Complexity: O(n), for storing the adjacency list and recursion stack.

Try this approach in the editor →

Approach 2: BFS Alternative Strategy

Though less intuitive for this problem compared to DFS, a Breadth-First Search (BFS) approach can be implemented to calculate the shortest paths considering leaf nodes. This method explores layers of the tree level by level but is not more efficient in this specific context than DFS, given that we only need to find necessary paths.

This problem inherently suits DFS; BFS would involve using a queue to track nodes but isn't optimal for path-related recursion required here.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) in BFS general terms, still visiting nodes.
Space Complexity: O(n), by the queue usage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS Traversal with Backtracking

Time Complexity: O(n), where n is the number of vertices. We explore each vertex once in the DFS traversal.
Space Complexity: O(n), for storing the adjacency list and recursion stack.

BFS Alternative Strategy

Time Complexity: O(n) in BFS general terms, still visiting nodes.
Space Complexity: O(n), by the queue usage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Traversal with BacktrackingO(n)O(n)Best general solution for tree problems where subtree information determines whether edges should be included
BFS with Parent Path ReconstructionO(n)O(n)Useful when parent relationships or level-order traversal are already required

Video Solution

Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python • NeetCodeIO • 25,813 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Time to Collect All Apples in a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters