We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Collect All Apples in a Tree

Difficulty: Medium

Problem Description

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, and there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple.

Key Insights

  • The tree structure allows for a straightforward traversal using Depth-First Search (DFS).
  • Only paths to vertices containing apples need to be traversed, reducing unnecessary travel.
  • Each edge to a vertex with an apple contributes a total travel time of 2 seconds (to and from).
  • If there are no apples in the tree, the minimum time is zero.

Space and Time Complexity

Time Complexity: O(n) - We traverse each node once in the DFS. Space Complexity: O(n) - The space is used for the adjacency list representation of the tree and the recursion stack.

Solution

We can use Depth-First Search (DFS) to explore the tree. The algorithm will check each node to see if it has an apple. If a node has an apple or if any of its children have apples, we will count the time to travel to that node and back, which is 2 seconds for each edge traversed. The base case of the recursion will handle leaves that do not contribute to additional travel time if they do not have apples.

Code Solutions

def minTime(n, edges, hasApple):
    # Build the adjacency list for the tree
    from collections import defaultdict

    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    def dfs(node, parent):
        time = 0
        for neighbor in graph[node]:
            if neighbor != parent:  # Avoid going back to the parent node
                child_time = dfs(neighbor, node)  # Recur for child nodes
                if child_time > 0 or hasApple[neighbor]:  # If child has apple or its subtree has apples
                    time += child_time + 2  # Add time to go to child and back
        return time

    return dfs(0, -1)  # Start DFS from node 0 with no parent
← Back to All Questions