Minimum TIme to Collect All apples in a Tree

XXX. Minimum Time to Collect All Apples in a Tree

Tree

Depth-First Search

Problem Statement:

You are given an undirected tree consisting of n nodes numbered from 0 to n-1, which has n-1 edges. The root of the tree is node 0, and each node has one or zero apples associated with it. Return the minimum time in seconds you need to collect all apples in the tree starting at the root and coming back to the root.

Algorithm:

1. Create an adjacency list to represent the tree structure from the edge list.
2. Use Depth-First Search (DFS) to traverse the tree starting from the root (node 0).
3. At each node:
   • Recur on its children (ignore the parent to avoid cycles).
   • If any child subtree contains an apple or the current node has an apple, add the time to visit and return from that subtree.
4. Return the total time required for traversal.

Complexity:

Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the adjacency list and recursive call stack.

Java Implementation:

import java.util.*;

public class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        // Build adjacency list from edge list
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            adj.computeIfAbsent(a, value -> new ArrayList<>()).add(b);
            adj.computeIfAbsent(b, value -> new ArrayList<>()).add(a);
        }
        // Start DFS from the root node (0) with no parent (-1)
        return dfs(0, -1, adj, hasApple);
    }

    public int dfs(int node, int parent, Map<Integer, List<Integer>> adj, List<Boolean> hasApple) {
        if (!adj.containsKey(node)) // Leaf node
            return 0;

        int totalTime = 0;
        for (int child : adj.get(node)) {
            if (child == parent) // Avoid going back to the parent
                continue;
            int childTime = dfs(child, node, adj, hasApple);
            // Add the cost of visiting and returning from the subtree if it has apples
            if (childTime > 0 || hasApple.get(child)) {
                totalTime += childTime;
                totalTIme += 2;
            }
        }
        return totalTime;
    }
}

Examples:

🔗

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

🔗

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