1443. Minimum Time to Collect All Apples in a Tree - Explanation

Description

You are given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend one 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 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 path that takes minimum time to collect all apples is: 0 -> 1 -> 4 -> 1 -> 5 -> 1 -> 0 -> 2 -> 0.

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 path that takes minimum time to collect all apples is: 0 -> 2 -> 0 -> 1 -> 5 -> 1 -> 0.

Constraints:

1 <= n <= 100,000
edges.length == n - 1
edges[i].length == 2
0 <= a[i] < b[i] <= n - 1
hasApple.length == n

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Tree Data Structure - Understanding parent-child relationships and traversing trees represented as edge lists
Depth First Search (DFS) on Trees - Recursively exploring tree nodes while tracking the parent to avoid revisiting
Topological Sort (Kahn's Algorithm) - Processing nodes from leaves to root using indegree tracking and a queue

1. Depth First Search

Intuition

We start at node 0 and need to visit all nodes that have apples. The key observation is that if a subtree contains any apple (either at the child node itself or deeper in the subtree), we must traverse the edge to that child and back, costing 2 seconds. We use DFS to compute the time needed for each subtree. If a child has an apple or its subtree requires time (meaning there's an apple deeper), we add 2 plus the child's subtree time to our current total.

Algorithm

Build an adjacency list from the edges (undirected tree).
Run DFS from node 0 with parent tracking to avoid revisiting:
- For each child (excluding parent):
  - Recursively compute childTime for that subtree.
  - If childTime > 0 or the child has an apple, add 2 + childTime to the current time.
- Return the accumulated time for this subtree.
Return the result of dfs(0, -1).

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        adj = {i: [] for i in range(n)}
        for par, child in edges:
            adj[par].append(child)
            adj[child].append(par)

        def dfs(cur, par):
            time = 0
            for child in adj[cur]:
                if child == par:
                    continue
                childTime = dfs(child, cur)
                if childTime > 0 or hasApple[child]:
                    time += 2 + childTime
            return time

        return dfs(0, -1)

public class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        return dfs(0, -1, adj, hasApple);
    }

    private int dfs(int cur, int parent, List<Integer>[] adj, List<Boolean> hasApple) {
        int time = 0;
        for (int child : adj[cur]) {
            if (child == parent) continue;
            int childTime = dfs(child, cur, adj, hasApple);
            if (childTime > 0 || hasApple.get(child)) {
                time += 2 + childTime;
            }
        }
        return time;
    }
}

class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> adj(n);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        return dfs(0, -1, adj, hasApple);
    }

private:
    int dfs(int cur, int parent, vector<vector<int>>& adj, vector<bool>& hasApple) {
        int time = 0;
        for (int child : adj[cur]) {
            if (child == parent) continue;
            int childTime = dfs(child, cur, adj, hasApple);
            if (childTime > 0 || hasApple[child]) {
                time += 2 + childTime;
            }
        }
        return time;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} edges
     * @param {boolean[]} hasApple
     * @return {number}
     */
    minTime(n, edges, hasApple) {
        const adj = Array.from({ length: n }, () => []);
        for (const [parent, child] of edges) {
            adj[parent].push(child);
            adj[child].push(parent);
        }

        const dfs = (cur, parent) => {
            let time = 0;
            for (const child of adj[cur]) {
                if (child === parent) continue;
                const childTime = dfs(child, cur);
                if (childTime > 0 || hasApple[child]) {
                    time += 2 + childTime;
                }
            }
            return time;
        };

        return dfs(0, -1);
    }
}

func minTime(n int, edges [][]int, hasApple []bool) int {
    adj := make([][]int, n)
    for i := range adj {
        adj[i] = []int{}
    }
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
    }

    var dfs func(cur, parent int) int
    dfs = func(cur, parent int) int {
        time := 0
        for _, child := range adj[cur] {
            if child == parent {
                continue
            }
            childTime := dfs(child, cur)
            if childTime > 0 || hasApple[child] {
                time += 2 + childTime
            }
        }
        return time
    }

    return dfs(0, -1)
}

class Solution {
    fun minTime(n: Int, edges: Array<IntArray>, hasApple: List<Boolean>): Int {
        val adj = Array(n) { mutableListOf<Int>() }
        for (edge in edges) {
            adj[edge[0]].add(edge[1])
            adj[edge[1]].add(edge[0])
        }

        fun dfs(cur: Int, parent: Int): Int {
            var time = 0
            for (child in adj[cur]) {
                if (child == parent) continue
                val childTime = dfs(child, cur)
                if (childTime > 0 || hasApple[child]) {
                    time += 2 + childTime
                }
            }
            return time
        }

        return dfs(0, -1)
    }
}

class Solution {
    func minTime(_ n: Int, _ edges: [[Int]], _ hasApple: [Bool]) -> Int {
        var adj = [[Int]](repeating: [], count: n)
        for edge in edges {
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])
        }

        func dfs(_ cur: Int, _ parent: Int) -> Int {
            var time = 0
            for child in adj[cur] {
                if child == parent { continue }
                let childTime = dfs(child, cur)
                if childTime > 0 || hasApple[child] {
                    time += 2 + childTime
                }
            }
            return time
        }

        return dfs(0, -1)
    }
}

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.

2. Topological Sort (Kahn's Algorithm)

Intuition

Instead of top-down DFS, we can process the tree from leaves to root. Starting from leaf nodes (nodes with only one connection, excluding the root), we propagate the time upward. If a leaf has an apple or already accumulated time from its subtree, we add 2 seconds to its parent. This bottom-up approach naturally handles the aggregation of times from multiple subtrees.

Algorithm

Build an adjacency list and track the degree (number of connections) for each node.
Initialize a queue with all leaf nodes (degree 1, excluding node 0).
Process nodes in the queue:
- For each neighbor of the current node with positive degree:
  - Decrement the neighbor's degree.
  - If the current node has an apple or has accumulated time, add time[node] + 2 to time[neighbor].
  - If the neighbor becomes a leaf (degree 1) and isn't the root, add it to the queue.
Return time[0].

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

        queue = deque()
        for i in range(1, n):
            if indegree[i] == 1:
                queue.append(i)
                indegree[i] = 0

        time = [0] * n
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                if indegree[nei] <= 0:
                    continue

                indegree[nei] -= 1
                if hasApple[node] or time[node] > 0:
                    time[nei] += time[node] + 2
                if indegree[nei] == 1 and nei != 0:
                    queue.append(nei)

        return time[0]

public class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        int[] indegree = new int[n];
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
            indegree[edge[0]]++;
            indegree[edge[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < n; i++) {
            if (indegree[i] == 1) {
                queue.offer(i);
                indegree[i] = 0;
            }
        }

        int[] time = new int[n];
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : adj[node]) {
                if (indegree[neighbor] <= 0) {
                    continue;
                }

                indegree[neighbor]--;
                if (hasApple.get(node) || time[node] > 0) {
                    time[neighbor] += time[node] + 2;
                }
                if (indegree[neighbor] == 1 && neighbor != 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return time[0];
    }
}

class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> adj(n);
        vector<int> indegree(n, 0);

        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
            indegree[edge[0]]++;
            indegree[edge[1]]++;
        }

        queue<int> q;
        for (int i = 1; i < n; ++i) {
            if (indegree[i] == 1) {
                q.push(i);
                indegree[i] = 0;
            }
        }

        vector<int> time(n, 0);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int neighbor : adj[node]) {
                if (indegree[neighbor] <= 0) {
                    continue;
                }

                indegree[neighbor]--;
                if (hasApple[node] || time[node] > 0) {
                    time[neighbor] += time[node] + 2;
                }
                if (indegree[neighbor] == 1 && neighbor != 0) {
                    q.push(neighbor);
                }
            }
        }

        return time[0];
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} edges
     * @param {boolean[]} hasApple
     * @return {number}
     */
    minTime(n, edges, hasApple) {
        const adj = Array.from({ length: n }, () => []);
        const indegree = Array(n).fill(0);

        for (const [u, v] of edges) {
            adj[u].push(v);
            adj[v].push(u);
            indegree[u]++;
            indegree[v]++;
        }

        const queue = new Queue();
        for (let i = 1; i < n; i++) {
            if (indegree[i] === 1) {
                queue.push(i);
                indegree[i] = 0;
            }
        }

        const time = Array(n).fill(0);
        while (!queue.isEmpty()) {
            const node = queue.pop();
            for (const neighbor of adj[node]) {
                if (indegree[neighbor] <= 0) {
                    continue;
                }

                indegree[neighbor]--;
                if (hasApple[node] || time[node] > 0) {
                    time[neighbor] += time[node] + 2;
                }
                if (indegree[neighbor] === 1 && neighbor !== 0) {
                    queue.push(neighbor);
                }
            }
        }

        return time[0];
    }
}

func minTime(n int, edges [][]int, hasApple []bool) int {
    adj := make([][]int, n)
    for i := range adj {
        adj[i] = []int{}
    }
    indegree := make([]int, n)
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
        indegree[edge[0]]++
        indegree[edge[1]]++
    }

    queue := []int{}
    for i := 1; i < n; i++ {
        if indegree[i] == 1 {
            queue = append(queue, i)
            indegree[i] = 0
        }
    }

    time := make([]int, n)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, nei := range adj[node] {
            if indegree[nei] <= 0 {
                continue
            }
            indegree[nei]--
            if hasApple[node] || time[node] > 0 {
                time[nei] += time[node] + 2
            }
            if indegree[nei] == 1 && nei != 0 {
                queue = append(queue, nei)
            }
        }
    }

    return time[0]
}

class Solution {
    fun minTime(n: Int, edges: Array<IntArray>, hasApple: List<Boolean>): Int {
        val adj = Array(n) { mutableListOf<Int>() }
        val indegree = IntArray(n)
        for (edge in edges) {
            adj[edge[0]].add(edge[1])
            adj[edge[1]].add(edge[0])
            indegree[edge[0]]++
            indegree[edge[1]]++
        }

        val queue = ArrayDeque<Int>()
        for (i in 1 until n) {
            if (indegree[i] == 1) {
                queue.add(i)
                indegree[i] = 0
            }
        }

        val time = IntArray(n)
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            for (nei in adj[node]) {
                if (indegree[nei] <= 0) continue
                indegree[nei]--
                if (hasApple[node] || time[node] > 0) {
                    time[nei] += time[node] + 2
                }
                if (indegree[nei] == 1 && nei != 0) {
                    queue.add(nei)
                }
            }
        }

        return time[0]
    }
}

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.

Common Pitfalls

Not Tracking Parent Nodes

Since the tree is given as an undirected edge list, each edge appears in both directions in the adjacency list. Without tracking the parent node during DFS, you will revisit the parent as if it were a child, causing infinite recursion or incorrect double-counting of edges. Always pass the parent node to recursive calls and skip it when iterating through neighbors.

Counting Edges Instead of Round Trips

Each edge must be traversed twice (once going down to collect apples, once coming back up). A common mistake is adding 1 instead of 2 to the time when an edge needs to be traversed. This results in answers that are exactly half of the correct value.

Ignoring Apples in Subtrees

Some solutions only check if the current child node has an apple, forgetting that we also need to traverse to a child if its subtree contains apples deeper down. The correct condition is: traverse to a child if hasApple[child] is true OR if childTime > 0 (meaning the subtree required time, indicating apples exist deeper).