Minimum Time to Collect All Apples in a Tree

Med

#1334Time: O(N + k * H), where N is the number of vertices, k is the number of apples, and H is the height of the tree. In the worst-case scenario (a skewed tree where k and H are both O(N)), the complexity becomes O(N^2).Space: O(N), where N is the number of vertices. This is for storing the adjacency list, the `parent` array, the BFS queue, and the `HashSet` of required edges.1 company

Algorithms

Depth-First Search Breadth-First Search

Data structures

Hash Table Tree

Companies

Myntra

Prompt

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] = [a_i, b_i] 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 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 <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i < b_i <= n - 1
hasApple.length == n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of collecting apples. It first identifies all nodes with apples. Then, for each of these nodes, it determines the path from the root (vertex 0). By combining all such paths, it identifies the set of all unique edges that must be traversed. The total time is simply twice the number of these unique edges, accounting for the round trip.

Algorithm

Build an adjacency list representation of the tree from the edges array.
Perform a Breadth-First Search (BFS) starting from vertex 0 to compute the parent of each node in the shortest path from the root. Store these in a parent array.
Initialize an empty HashSet to store the unique edges that must be traversed.
Iterate through all vertices. If a vertex i has an apple (hasApple[i] is true):
- Trace the path from i back to the root (vertex 0) using the parent array.
- For each edge on this path, add a canonical representation of the edge to the HashSet to ensure uniqueness.
The total time is the number of unique edges in the set multiplied by 2, as each edge must be traversed down and back up.

Walkthrough

First, we need a way to represent the tree. An adjacency list is a suitable choice, built from the given edges. To find the path from the root to each apple, we can pre-compute the parent of each node in the path from the root. A Breadth-First Search (BFS) starting from vertex 0 is perfect for this.

Once we have the parent array, we can iterate through all nodes. If a node i contains an apple, we trace its path back to the root by repeatedly moving to its parent (curr = parent[curr]) until we reach vertex 0. During this traversal, we add each edge to a HashSet. Using a HashSet automatically handles the counting of unique edges.

Finally, the size of the HashSet gives us the number of unique edges on the required paths. Since every such edge must be traversed once to go away from the root and once to come back, the total time is 2 * set.size().

1import java.util.*;2 3class Solution {4    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {5        List<List<Integer>> adj = new ArrayList<>();6        for (int i = 0; i < n; i++) {7            adj.add(new ArrayList<>());8        }9        for (int[] edge : edges) {10            adj.get(edge[0]).add(edge[1]);11            adj.get(edge[1]).add(edge[0]);12        }13 14        int[] parent = new int[n];15        Arrays.fill(parent, -1);16        Queue<Integer> queue = new LinkedList<>();17        queue.offer(0);18        boolean[] visited = new boolean[n];19        visited[0] = true;20 21        while (!queue.isEmpty()) {22            int u = queue.poll();23            for (int v : adj.get(u)) {24                if (!visited[v]) {25                    visited[v] = true;26                    parent[v] = u;27                    queue.offer(v);28                }29            }30        }31 32        Set<Long> requiredEdges = new HashSet<>();33        for (int i = 0; i < n; i++) {34            if (hasApple.get(i)) {35                int curr = i;36                while (curr != 0) {37                    int p = parent[curr];38                    long u = Math.min(p, curr);39                    long v = Math.max(p, curr);40                    requiredEdges.add(u * n + v);41                    curr = p;42                }43            }44        }45 46        return requiredEdges.size() * 2;47    }48}

Complexity

Time

O(N + k * H), where N is the number of vertices, k is the number of apples, and H is the height of the tree. In the worst-case scenario (a skewed tree where k and H are both O(N)), the complexity becomes O(N^2).

Space

O(N), where N is the number of vertices. This is for storing the adjacency list, the `parent` array, the BFS queue, and the `HashSet` of required edges.

Trade-offs

Pros

The logic is straightforward and easy to understand as it directly models the problem statement.
It correctly solves the problem for smaller inputs.

Cons

The time complexity is quadratic in the worst-case, which is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.
It's more complex to implement compared to the optimal DFS solution, requiring multiple data structures (adjacency list, parent array, queue for BFS, and a set for edges).

This optimal approach uses a single Depth-First Search (DFS) traversal to calculate the minimum time. The core idea is to think about the problem recursively. For any subtree, we only need to enter it if it contains an apple. The DFS function, when called on a node u, calculates the total time spent collecting apples within the subtrees of its children. It adds 2 seconds (for the round trip) for each edge leading to a child's subtree that must be visited.

Algorithm

Build an adjacency list representation of the tree from the edges array.
Create a recursive Depth-First Search (DFS) function, say dfs(currentNode, parentNode).
This function will return the time required to collect all apples in the subtree of currentNode and return to currentNode.
In the dfs function for node u:
- Initialize a variable subtreeTime = 0.
- Iterate through all neighbors v of u (excluding its parent).
- Recursively call childTime = dfs(v, u).
- If the child's subtree contains any apples (childTime > 0) or if the child node v itself has an apple, it means we must traverse the edge (u, v). Add childTime + 2 to subtreeTime. The +2 accounts for moving from u to v and back.
- Return subtreeTime.
The final answer is the result of the initial call dfs(0, -1).

Walkthrough

We can solve this problem efficiently in one pass using DFS. First, we represent the tree using an adjacency list. Then, we start a DFS from the root, vertex 0.

We define a recursive function dfs(u, parent) that returns the time needed to collect apples in the subtree rooted at u and come back to u. For each child v of u, we recursively call dfs(v, u). Let's say this call returns childTime. If childTime > 0, it means there were apples in v's subtree, and childTime is the time spent inside that subtree. If hasApple.get(v) is true, it means node v itself has an apple. In either of these cases, we must travel from u to v. This trip costs 2 seconds (1 to go, 1 to return), plus the childTime spent within v's subtree. So, we add childTime + 2 to the total time for u's subtree.

If a child's subtree has no apples and the child itself doesn't have one (childTime == 0 and !hasApple.get(v)), we don't need to visit it, and it contributes zero time. The final answer is the result of dfs(0, -1).

1import java.util.*;2 3class Solution {4    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {5        List<List<Integer>> adj = new ArrayList<>();6        for (int i = 0; i < n; i++) {7            adj.add(new ArrayList<>());8        }9        for (int[] edge : edges) {10            adj.get(edge[0]).add(edge[1]);11            adj.get(edge[1]).add(edge[0]);12        }13 14        return dfs(0, -1, adj, hasApple);15    }16 17    private int dfs(int u, int parent, List<List<Integer>> adj, List<Boolean> hasApple) {18        int totalTime = 0;19        for (int v : adj.get(u)) {20            if (v == parent) {21                continue;22            }23            int childTime = dfs(v, u, adj, hasApple);24            if (childTime > 0 || hasApple.get(v)) {25                totalTime += childTime + 2;26            }27        }28        return totalTime;29    }30}

Complexity

Time

O(N), where N is the number of vertices. Both building the adjacency list and the DFS traversal take linear time, as each vertex and edge is visited once.

Space

O(N), where N is the number of vertices. O(N) is used for the adjacency list. The recursion stack for DFS can also go up to O(N) in the worst case of a skewed tree.

Trade-offs

Pros

Extremely efficient, with a linear time complexity that passes all constraints.
Solves the problem in a single traversal of the tree.
The implementation is clean and concise.

Cons

The recursive nature of the solution might be slightly less intuitive at first glance compared to a more direct, iterative approach.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem