LeetCode 1443 - Minimum Time to Collect All Apples in a Tree

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem is asking for the minimum time required to collect all apples in a tree, where each edge traversal takes 1 second. You start and end at vertex 0. The tree is given as an undirected graph with n vertices, described using an edges array. Each edge connects two vertices ai and bi. A boolean array hasApple indicates whether each vertex contains an apple.

The key here is that you only need to traverse edges that are on paths to vertices with apples. You do not need to visit vertices without apples unless they are on the path to some vertex that does contain an apple. Returning to the root means that the total time will count each edge traversal twice if it is on a necessary path.

The constraints tell us that the tree can be very large (n up to 10^5), so any algorithm that is worse than linear time with respect to n may be too slow. The tree is always valid, meaning there are no cycles and edges.length = n - 1.

Important edge cases include trees where no vertices have apples, trees where all vertices have apples, and trees that are highly unbalanced (e.g., a chain), which could affect recursion or traversal logic.

Approaches

A brute-force approach would involve generating all possible paths starting from vertex 0 and visiting every vertex with an apple. For each path, you would compute the total distance, then pick the minimum. This approach is obviously too slow for large n because the number of paths grows exponentially with the number of vertices.

The key insight for an optimal solution is that you only need to visit vertices that either have apples or are on the path to an apple. Therefore, a Depth-First Search (DFS) can be used to compute the total time recursively. For each subtree, if it contains an apple or any of its descendants contain an apple, you add the cost of traversing that edge twice (going down and coming back). If neither the node nor its descendants contain an apple, you skip it entirely.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generate all possible paths visiting apple vertices, exponential runtime
Optimal DFS	O(n)	O(n)	Traverse each node once, only include edges necessary to collect apples

Algorithm Walkthrough

Build an adjacency list representation of the tree from the edges array. This allows efficient traversal from a node to its neighbors.
Define a recursive DFS function that takes the current node and its parent. The parent ensures we do not revisit the node we just came from, maintaining a tree traversal without cycles.
Initialize a counter total_time inside the DFS function. This will accumulate the time for collecting apples in the subtree rooted at the current node.
For each child of the current node (skipping the parent), recursively call the DFS function.
Add the returned subtree time to total_time.
After traversing all children, check if the current node has an apple or if total_time from children is greater than 0. If so, and the current node is not the root, add 2 seconds for the edge leading from the parent to this node.
Return total_time.
Call DFS starting from the root node 0 with parent -1 and return the result as the minimum time.

Why it works: This algorithm works because it correctly accumulates the total time only for edges that are on paths to apples. Edges without apples in their subtree are never counted, ensuring minimal total time.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)

        def dfs(node: int, parent: int) -> int:
            total_time = 0
            for child in tree[node]:
                if child == parent:
                    continue
                child_time = dfs(child, node)
                total_time += child_time
            if (node != 0 and (hasApple[node] or total_time > 0)):
                total_time += 2
            return total_time

        return dfs(0, -1)

In this implementation, we first build an adjacency list to represent the tree efficiently. The dfs function traverses each node exactly once, computing the time needed to collect apples in its subtree. The check (node != 0 and (hasApple[node] or total_time > 0)) ensures that we only add the edge cost if necessary and skip adding it for the root.

Go Solution

package main

func minTime(n int, edges [][]int, hasApple []bool) int {
    tree := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        tree[u] = append(tree[u], v)
        tree[v] = append(tree[v], u)
    }

    var dfs func(node, parent int) int
    dfs = func(node, parent int) int {
        totalTime := 0
        for _, child := range tree[node] {
            if child == parent {
                continue
            }
            totalTime += dfs(child, node)
        }
        if node != 0 && (hasApple[node] || totalTime > 0) {
            totalTime += 2
        }
        return totalTime
    }

    return dfs(0, -1)
}

The Go solution is similar to Python. We use slices to store adjacency lists and a recursive closure for DFS. The dfs function accumulates time just like in Python, and parent checks avoid revisiting the previous node.

Worked Examples

Example 1

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

DFS traversal:

Start at 0, visit 1 and 2
Node 1: child 4 has apple → add 2, child 5 has apple → add 2, total_time at 1 = 4 → add 2 to go from 0 → total_time = 6
Node 2: child 3 no apple, child 6 no apple, node 2 has apple → add 2 → total_time = 2 → add 2 to go from 0 → total_time = 4
Total = 6 + 4 = 10 (but double-count? Wait carefully)
Correct traversal adds 2 for each necessary edge only once. Total = 8

Example 2

hasApple = [false,false,true,false,false,true,false]

Only nodes 2 and 5 have apples
Path: 0→2→return, 0→1→5→return
Total edges traversed = 3 edges each counted twice → 6

Example 3

hasApple = [false,false,false,false,false,false,false]

No apples, DFS returns 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once in DFS
Space	O(n)	Adjacency list plus recursion stack

The linear time complexity is achievable because each edge is traversed at most twice, and we only process each node once. The space complexity is linear due to storing the tree and the recursion stack.

Test Cases

# Provided examples
assert Solution().minTime(7, [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], [False,False,True,False,True,True,False]) == 8
assert Solution().minTime(7, [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], [False,False,True,False,False,True,False]) == 6
assert Solution().minTime(7, [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], [False,False,False,False,False,False,False]) == 0

# Edge cases
assert Solution().minTime(1, [], [True]) == 0  # Only root with apple, no edge to traverse
assert Solution().minTime(2, [[0,1]], [True, True]) == 2  # Two nodes both have apples
assert Solution().minTime(2, [[0,1]], [False, True]) == 2  # Only child has apple
assert Solution().minTime(3, [[0,1],[1,2]], [False, False, True]) == 4  # Linear chain, last node has apple

Test	Why
All examples	Validates expected output correctness
Single node	Ensures edge case of no edges is handled
Two nodes	Tests minimal tree size with apples at different positions
Linear chain	Confirms correct handling of unbalanced trees

Edge Cases

Single-node tree with apple: If the tree has only vertex 0 and it has an apple, no edges need traversal. The implementation correctly returns 0 since no total_time is added for the root.

Linear chain tree: In a chain