Minimum Time to Collect All Apples in a Tree

Minimum Time to Collect All Apples in a Tree - Problem

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.

Input & Output

Example 1 — Basic Tree

$ 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

💡 Note: Start at 0. Go to node 2 (2 seconds), collect apple at node 2, then go to node 3 (2 seconds), return to 2 (2 seconds), then return to 0 (2 seconds). Total: 8 seconds.

Example 2 — Single Apple

$ 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

💡 Note: No apples to collect, so no need to move from starting position. Total: 0 seconds.

Example 3 — All Apples

$ Input: n = 4, edges = [[0,1],[1,2],[0,3]], hasApple = [true,true,true,true]

› Output: 6

💡 Note: Must visit all nodes: 0→1→2 (return to 1, then 0), then 0→3 (return to 0). Path: 0→1→2→1→0→3→0. Total: 6 seconds.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
edges[i].length == 2
0 ≤ ai, bi ≤ n - 1
ai ≠ bi
hasApple.length == n

Visualization

Tap to expand

Understanding the Visualization

Tree Structure

Build adjacency list from edges array

DFS Traversal

Use DFS to check which subtrees have apples

Optimal Path

Only visit branches that contain apples

Key Takeaway

🎯 Key Insight: Only traverse subtrees containing apples using DFS, avoiding unnecessary branches

Asked in

G Google 25 a Amazon 18 M Microsoft 15 🍎 Apple 12

The key insight is to use DFS to only traverse subtrees that contain at least one apple, avoiding unnecessary branches. The optimal approach uses recursive DFS to check if a subtree has apples before visiting it. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Apple-aware Pruning	O(n)	O(n)	Use DFS to only traverse subtrees that contain apples
Brute Force - Visit All Paths	O(n²)	O(n)	Visit every possible path in the tree, whether it has apples or not

DFS with Apple-aware Pruning — Algorithm Steps

Build adjacency list from edges
DFS from root, checking if subtree has apples
Only traverse edges leading to apple-containing subtrees
Count 2 seconds for each useful edge (go and return)

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from edges

DFS Traversal

Check each subtree for apples before visiting

Optimal Path

Only traverse edges leading to apples

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dfs(int node, int parent, int** graph, int* graphSize, int* hasApple) {
    int timeNeeded = 0;
    
    // Check all children
    for (int i = 0; i < graphSize[node]; i++) {
        int child = graph[node][i];
        if (child != parent) {
            int childTime = dfs(child, node, graph, graphSize, hasApple);
            // If child subtree has apples, we need to visit it
            if (childTime > 0 || hasApple[child]) {
                timeNeeded += childTime + 2; // 2 for going to child and back
            }
        }
    }
    
    return timeNeeded;
}

int solution(int n, int** edges, int edgesSize, int* hasApple) {
    if (n <= 1) return 0;
    
    // Build adjacency list
    int** graph = (int**)malloc(n * sizeof(int*));
    int* graphSize = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    int result = dfs(0, -1, graph, graphSize, hasApple);
    
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSize);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simple demo - would need proper JSON parsing
    printf("%d\n", 0);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node at most once during DFS traversal

✓ Linear Growth

Space Complexity

O(n)

Adjacency list storage and recursion stack depth up to n

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Apple-aware Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler