Leetcode #1443: Minimum Time to Collect All Apples in a Tree

Link to the Problem

Minimum Time to Collect All Apples in a Tree

Thought Process

Whenever you are at a node, say p, you will collect all apples in p’s subtree before returning back to the original root. This will avoid traveling the same path multiple times.
Say, root is where we start, p is a node in the tree and p has two children – child1, child2 – and both of them have an apple each.
root -> p -> child1 -> p -> child2 -> p -> root is always going to be better than root -> p -> child1 -> p -> root -> p -> child2 -> p -> root.

Secondly, time required to travel each edge can be assumed to be 2 because it takes 1 unit time to travel each way. At the end, we must go back to the root as the problem statement states, so we can assume time to be 2 and the direction to be one way. In other words, we can also say that the time required to visit each node is 2 units. We start at root, so for the root, time will be 0.

Algorithm

  1. Because you have the list of edges, construct a better representation – adjacency list – of the tree.
  2. Start with the root.
    1. Find the time required to collect apples in the subtree of each child of the node. Repeat this recursively.
    2. If there is at least one child in the subtree, we have to collect it. So we will also have to add the time required to visit the every node on the path i.e. current node.
  3. return the total time.
Leetcode #1443: Minimum Time to Collect All Apples in a Tree - Leetcode Solutions - Problem Solving
Leetcode #1443: Minimum Time to Collect All Apples in a Tree – Diagram to assist visualization

Code

class Solution {
unordered_map<int, vector<int>> tree;
unordered_map<int, bool> visited;
vector<bool> hasApple;
/** Convert edge list into adjacency list */
void createTreeStructure(vector<vector<int>>& edges) {
// Adjacency list representation.
for (auto e: edges) {
tree[e[0]].push_back(e[1]); // a --> b
tree[e[1]].push_back(e[0]); // b --> a
}
}
/** Returns time required to collect apples in the subtree of the 'node'. */
int traverse(int node, int timeToVisitNode) {
if (visited[node]) { // Already visited this node and its subtree.
return 0; // So no need to visit again.
}
visited[node] = true; // Mark visited to avoid repetition.
int subtreeTime = 0; // Time required to collect apples in subtree.
for (auto childNode: tree[node]) {
subtreeTime += traverse(childNode, /* timeToVisitNode= */ 2);
}
// If the subtree has no apples, subtree time will be 0. And
// if the current node also does not have an apple, then we can
// simply avoid traversing the current branch of the tree to save
// the time. In that case, time required for this subtree will be 0.
if (subtreeTime == 0 && hasApple[node] == false) {
return 0;
}
return subtreeTime + timeToVisitNode;
}
public:
int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
this->hasApple = hasApple;
createTreeStructure(edges);
// Time to visit any node is 2 except 0.
return traverse(/* startNode= */ 0, /* timeToVisitNode= */ 0);
}
};
view raw Leetcode_1443.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

Similar Problems

Leetcode #543: Diameter of Binary Tree
Leetcode #110: Balanced Binary Tree



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s