Minimum Time to Collect All Apples in a Tree solution and explanation

class Solution:
    def minTime(self, n, edges, hasApple):
        from collections import defaultdict
        adj = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        return self.dfs(0, -1, adj, hasApple)

    def dfs(self, node, parent, adj, hasApple):
        total_time = 0
        for child in adj[node]:
            if child == parent:
                continue
            child_time = self.dfs(child, node, adj, hasApple)
            if child_time > 0 or hasApple[child]:
                total_time += child_time + 2
        return total_time

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        return dfs(0, -1, adj, hasApple);
    }
    
    private int dfs(int node, int parent, List<List<Integer>> adj, List<Boolean> hasApple) {
        int total_time = 0;
        for (int child : adj.get(node)) {
            if (child == parent) continue;
            int child_time = dfs(child, node, adj, hasApple);
            if (child_time > 0 || hasApple.get(child)) {
                total_time += child_time + 2;
            }
        }
        return total_time;
    }
}

#include <vector>
using namespace std;

class Solution {
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(0, -1, adj, hasApple);
    }
    
    int dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& hasApple) {
        int total_time = 0;
        for (int child : adj[node]) {
            if (child == parent) continue;
            int child_time = dfs(child, node, adj, hasApple);
            if (child_time > 0 || hasApple[child]) total_time += child_time + 2;
        }
        return total_time;
    }
};

var minTime = function(n, edges, hasApple) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    return dfs(0, -1, adj, hasApple);
};

function dfs(node, parent, adj, hasApple) {
    let total_time = 0;
    for (const child of adj[node]) {
        if (child === parent) continue;
        const child_time = dfs(child, node, adj, hasApple);
        if (child_time > 0 || hasApple[child]) {
            total_time += child_time + 2;
        }
    }
    return total_time;
}

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int timeRequired = 0;

void dfs(int node, int parent, int** adjList, int* adjSize, bool* hasApple) {
    for (int i = 0; i < adjSize[node]; ++i) {
        int child = adjList[node][i];
        if (child == parent) continue;
        dfs(child, node, adjList, adjSize, hasApple);
        if (hasApple[child]) {
            timeRequired += 2;
            hasApple[node] = true;
        }
    }
}

int minTime(int n, int** edges, int edgesSize, bool* hasApple) {
    int* adjSize = (int*)calloc(n, sizeof(int));
    int** adjList = (int**)malloc(n * sizeof(int*));

    for (int i = 0; i < n; ++i) {
        adjList[i] = (int*)malloc((n - 1) * sizeof(int));
    }

    for (int i = 0; i < edgesSize; ++i) {
        int u = edges[i][0];
        int v = edges[i][1];
        adjList[u][adjSize[u]++] = v;
        adjList[v][adjSize[v]++] = u;
    }

    dfs(0, -1, adjList, adjSize, hasApple);

    for (int i = 0; i < n; ++i) {
        free(adjList[i]);
    }
    free(adjList);
    free(adjSize);

    return timeRequired;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int MinTime(int n, int[][] edges, IList<bool> hasApple) {
        List<int>[] adj = new List<int>[n];
        for (int i = 0; i < n; i++) adj[i] = new List<int>();
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        return DFS(0, -1, adj, hasApple);
    }
    
    private int DFS(int node, int parent, List<int>[] adj, IList<bool> hasApple) {
        int total_time = 0;
        foreach (int child in adj[node]) {
            if (child == parent) continue;
            int child_time = DFS(child, node, adj, hasApple);
            if (child_time > 0 || hasApple[child]) {
                total_time += child_time + 2;
            }
        }
        return total_time;
    }
}

/* Python's theoretical BFS equivalent involves queue usage. DFS is preferred, with its path-specific application. */

/* Java BFS using a queue and tracking visited nodes. Relies on comparison in broader algorithms, but DFS remains efficient for path decisions here. */

/* Similar note on C++ for BFS: Iterative approach using a queue structure. DFS remains more efficient and practical in this tree scenario. */

/* JavaScript's BFS hypothetical involves queue patterns not optimal here versus DFS offering precise path-recursivity. */

/* BFS approach is typically less optimal for this problem due to the nature of finding paths, thus not usually implemented. For consideration of completeness, a general template would involve a queue to explore nodes layer-wise. Ideal use here remains DFS. */

/* C# consideration of BFS utilizes a while-loop and queue but is secondary to the DFS primary usage for path-targeted efficiency. */

func minTime(n int, edges [][]int, hasApple []bool) int {
	vis := make([]bool, n)
	g := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		g[u] = append(g[u], v)
		g[v] = append(g[v], u)
	}
	var dfs func(int, int) int
	dfs = func(u, cost int) int {
		if vis[u] {
			return 0
		}
		vis[u] = true
		nxt := 0
		for _, v := range g[u] {
			nxt += dfs(v, 2)
		}
		if !hasApple[u] && nxt == 0 {
			return 0
		}
		return cost + nxt
	}
	return dfs(0, 0)
}