Difficulty: Medium
Category: Tree, DFS, BFS, Graph

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, vertex i does not have any apple.

Examples

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^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai < bi < n
  • fromi < toi
  • hasApple.length == n

Thinking Process

This problem can be solved using either DFS or BFS approaches. The key insight is that we only need to visit subtrees that contain apples or lead to apples.

DFS Approach (Optimal):

  1. Build adjacency list from edges
  2. DFS from root (0) with parent tracking to avoid cycles
  3. For each subtree, calculate time needed if it contains apples
  4. Return total time including 2 seconds per edge (going and coming back)

BFS Approach:

  1. Build adjacency list and parent mapping using BFS
  2. For each apple node, trace path back to root
  3. Count edges in the path, avoiding duplicates
  4. Return total time (2 seconds per unique edge)
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

Approach 1: DFS (Optimal)

class Solution {
private:
    int dfs(vector<vector<int>>& adj, vector<bool>& hasApple, int node, int parent) {
        int totalTime = 0;
        for(auto& child: adj[node]) {
            if(child == parent) continue;
            int childTime = dfs(adj, hasApple, child, node);
            if(childTime > 0 || hasApple[child]) totalTime += childTime + 2;
        }
        return totalTime;
    }
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> adj(n);
        for(auto& edge: edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        return dfs(adj, hasApple, 0, -1);
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: This problem can be solved using either DFS or BFS approaches. The key insight is that we only need to visit subtrees that contain apples or lead to apples.

How the code works:

  1. Build adjacency list from edges
  2. DFS from root (0) with parent tracking to avoid cycles
  3. For each subtree, calculate time needed if it contains apples
  4. Return total time including 2 seconds per edge (going and coming back)
  5. Build adjacency list and parent mapping using BFS
  6. For each apple node, trace path back to root

    Which Approach is More Optimal?

DFS Approach is more optimal for the following reasons:

  1. Single Pass: DFS solves the problem in one traversal
  2. No Extra Data Structures: Doesn’t need parent array or visited set
  3. Cleaner Logic: Directly calculates time during traversal
  4. Better Space Usage: Only uses recursion stack vs multiple arrays
  5. More Intuitive: Naturally handles the tree structure

BFS Approach Trade-offs:

  • Two Passes: Requires BFS + path tracing
  • More Memory: Uses parent array and visited set
  • Complex Logic: More complex path tracing logic

References

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Tree Structure: Undirected tree with n-1 edges
  2. Edge Cost: Each edge costs 2 seconds (going + coming back)
  3. Optimal Path: Only visit edges that lead to apples
  4. DFS Advantage: Natural fit for tree traversal problems
  5. Parent Tracking: Essential to avoid cycles in undirected graph