Minimum Time to Collect All Apples in a Tree — LC 1443 Deep Dive

Problem Statement#

LeetCode 1443 — Minimum Time to Collect All Apples in a Tree | Difficulty: Medium

Given an undirected tree with n nodes numbered 0 to n-1, rooted at node 0, and a boolean array hasApple where hasApple[i] is true if node i has an apple, return the minimum number of seconds required to collect all apples and return to node 0. Traversing each edge takes 1 second in each direction (2 seconds round-trip).

Constraints:

• 1 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• hasApple.length == n

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]
 
Tree structure:
        0
       / \
      1   2
     / \ / \
    4  5 3  6
         ^
         apple at 3? No. Apples at: 2(no), 4(yes), 5(yes), 3(no)... 
         hasApple = [F,F,T,F,T,T,F]
         so apples at nodes 2, 4, 5
 
Output: 8
Explanation: Optimal path visits 0->1->4->1->5->1->0->2->0, taking 8 seconds.

Example 2:

Input: n = 7,
       edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]],
       hasApple = [false,false,true,false,false,false,false]
 
Output: 4
Explanation: Only node 2 has an apple. Go 0->2->0 = 4 seconds.

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
Explanation: No apples — no travel needed.

Why This Problem Matters#

This problem is a classic example of conditional post-order DFS on an undirected tree — a pattern that appears frequently in system design simulations, resource collection problems, and scheduling. The key interview signal is knowing when to include a sub-path in the answer: only when there is something worth collecting in that direction. This "prune if empty" principle is directly applicable to tree pruning, garbage collection algorithms, and lazy evaluation in compilers.

The Core Insight#

Root the tree at node 0. Perform a post-order DFS: process all children before the current node. For each child subtree, compute the total cost to collect all apples within it and return to the child node. Include that cost in the parent's answer only if:

• The child's subtree cost is greater than zero (something was collected deeper), or
• The child node itself has an apple.

If you must visit a child, the cost is childCost + 2 (2 for the round-trip edge). Otherwise, skip the child entirely.

The formula: total += childCost + 2 whenever childCost > 0 OR hasApple[child].

Visual Dry Run#

n = 7, hasApple = [F, F, T, F, T, T, F]
 
        0
       / \
      1   2 (apple)
     / \
    4   5
  (apple)(apple)

DFS from node 4 (leaf, has apple):

• No children → returns 0
• Parent (node 1) sees: childCost=0, hasApple[4]=true → include: 0 + 2 = 2

DFS from node 5 (leaf, has apple):

• No children → returns 0
• Parent (node 1) sees: childCost=0, hasApple[5]=true → include: 0 + 2 = 2

DFS from node 1 (no apple, but subtree cost = 4):

• total = 2 + 2 = 4, returns 4
• Parent (node 0) sees: childCost=4 > 0 → include: 4 + 2 = 6

DFS from node 2 (has apple, no children with apples):

• No relevant children → returns 0
• Parent (node 0) sees: childCost=0, hasApple[2]=true → include: 0 + 2 = 2

At node 0: total = 6 + 2 = 8 ✓

Common Mistakes#

1. Forgetting to add 2 for the round-trip — Each edge traversal costs 1 second each way. A round-trip to a child and back costs 2 seconds, not 1.

2. Checking only hasApple[child] and missing deeper apples — If a child itself has no apple but its descendants do (childCost > 0), you still need to visit it. Always check both conditions: childCost > 0 OR hasApple[child].

3. Visiting the parent in DFS on undirected graph — The adjacency list includes both directions. Without tracking the parent node and skipping it, you will loop back up the tree infinitely.

4. Returning 2 from leaf nodes with apples — Leaf nodes return 0 to their parent. The parent adds 2 for its own round-trip. Leaf nodes do not add 2 themselves.

5. Using a directed adjacency list — The input edges are undirected. Build both adj[u].push(v) and adj[v].push(u), otherwise you will miss upward connections.

6. Not handling n = 1 — A single node has no edges. If it has an apple it is at node 0 (start), so the answer is always 0 regardless of hasApple[0].

Solutions#

# Python — post-order DFS on undirected tree
from collections import defaultdict
 
def minTime(n, edges, hasApple):
    # Build undirected adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
 
    def dfs(node, parent):
        total = 0
        for child in adj[node]:
            # Skip the edge we came from — this is undirected
            if child == parent:
                continue
            # Recursively get cost of collecting apples in child's subtree
            child_cost = dfs(child, node)
            # Only visit this child if it has an apple or its subtree does
            if child_cost > 0 or hasApple[child]:
                total += child_cost + 2   # +2 for round-trip on this edge
 
        return total   # total seconds spent within this subtree
 
    return dfs(0, -1)   # start at node 0 with no parent

// JavaScript — post-order DFS on undirected tree
function minTime(n, edges, hasApple) {
    // Build undirected adjacency list
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
 
    function dfs(node, parent) {
        let total = 0;
        for (const child of adj[node]) {
            // Skip the node we arrived from
            if (child === parent) continue;
 
            // Cost of collecting everything within child's subtree
            const childCost = dfs(child, node);
 
            // Visit this child only if it or its subtree has an apple
            if (childCost > 0 || hasApple[child]) {
                total += childCost + 2;   // round-trip on this edge costs 2
            }
        }
        return total;
    }
 
    return dfs(0, -1);   // root is node 0, no parent
}

Complexity Analysis#

Every node and edge is visited exactly once. The adjacency list takes O(n) space (n-1 edges × 2 directions). Recursion stack is O(n) in the worst case (a line-shaped tree).

Follow-up Questions#

• What if nodes have weights (apples at multiple nodes cost different amounts)? The DFS structure stays identical — simply accumulate weighted costs instead of boolean flags.
• What if the starting node is not 0? Re-root the tree at the given start node before DFS, or run DFS with the new root while tracking parent as before.
• Can you solve iteratively? Yes — use a topological-sort style BFS (process leaves first), accumulating costs bottom-up. Avoids recursion-stack overflow on very deep trees.

This Pattern Solves#

• Any tree path collection problem where you skip empty subtrees (garbage collection, resource harvesting)
• Post-order accumulation with conditional inclusion
• Minimum-cost traversal problems on undirected trees rooted at a fixed node
• Problems where the answer at a parent depends on whether children contribute anything

Key Takeaways#

• Use post-order DFS and include a child's subtree only if childCost > 0 OR hasApple[child] — conditional inclusion is the key optimization
• Each edge traversal costs 2 seconds (round-trip) — the cost to visit a child is childCost + 2
• Build an undirected adjacency list from the edges and skip the parent node during DFS to avoid loops
• Leaf nodes return 0 — the +2 is always added by the parent, not the child itself
• Time O(n) — each node and edge visited exactly once; Space O(n) — adjacency list and call stack
• A single-node tree always returns 0 — no edges to traverse
• This conditional-inclusion post-order pattern applies to any "collect resources and return" problem on undirected trees