Geek has developed an effective vaccine for the Coronavirus and he wants each of the N houses in Geek Land to have access to it. Given a binary tree where each node represents a house in Geek Land, find the minimum number of houses that should be supplied with the vaccine kit if one vaccine kit is sufficient for that house, its parent house, and its immediate child nodes.
Examples:
Input:
1
/ \
2 3
\
4
\
5
\
6
Output: 2
Explanation:
The vaccine kits should be supplied to house numbers 1 and 5.Input:
1
/ \
2 3
Output: 1
Explanation:
The vaccine kits should be supplied to house number 1.
Approach: This problem can be solved using dynamic programming.
- Create a hashtable to keep check of all the nodes visited.
- The recursive function should return the number of child nodes below which are unvisited.
- If the node is NULL, return 0. This will be our base condition.
- Create a counter variable to store the number of unvisited child nodes and initialize it by the recursive call for the left and the right child nodes.
- If the counter variable is zero, all the child nodes have been visited. If the current node is unvisited and it is not the root node we return 1 as there is one node i.e. the current node which is unvisited.
- If the current node is unvisited and the counter variable is also zero and if the current node is root node then we increment the answer by 1 and return 1.
- Otherwise, if the counter variable is greater than zero, we mark the parent node, current node, and the child nodes as visited and increment the answer by 1.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Structure of a tree nodestruct Node { int data; Node* left; Node* right; Node(int val) { data = val; left = right = NULL; }};// Function to implement the dpint solve(int& ans, Node* root, Node* parent, unordered_map<Node*, int>& dp){ // Base Condition if (root == 0) return 0; // Counter Variable to store the number // of unvisited child elements for // the current node int cnt = solve(ans, root->left, root, dp); cnt += solve(ans, root->right, root, dp); // If there are no unvisited child nodes if (cnt == 0) { // If the current node is root // node and unvisited increment // the answer by 1 if (dp[root] == 0 && parent == 0) { ans++; return 1; } // If the current node is unvisited // but it is not the root node if (dp[root] == 0) return 1; // If the current node is also visited return 0; } // If there are unvisited child nodes else { // Mark the current node, // parent node and child // nodes as visited if (root->left != 0) dp[root->left] = 1; if (root->right != 0) dp[root->right] = 1; dp[root] = 1; if (parent != 0) dp[parent] = 1; // Increment the answer by 1 ans++; // Return 0 as now we have marked // all nodes as visited return 0; }}// Function to find required vaccinesint supplyVaccine(Node* root){ unordered_map<Node*, int> dp; int ans = 0; // Passing parent of root // node as NULL to identify it solve(ans, root, 0, dp); return ans;}// Driver Codeint main(){ string treeString; Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->right->right = new Node(4); root->right->right->right = new Node(5); root->right->right->right->right = new Node(6); // Function call cout << supplyVaccine(root) << "\n"; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Structure of a tree node static class Node { int data; Node left; Node right; Node(int val) { data = val; left = right = null; } }; static int ans; static HashMap<Node, Integer> dp; // Function to implement the dp static int solve(Node root, Node parent) { // Base Condition if (root == null) return 0; // Counter Variable to store the number // of unvisited child elements for // the current node ans = solve(root.left, root); ans += solve(root.right, root); // If there are no unvisited child nodes if (ans == 0) { // If the current node is root // node and unvisited increment // the answer by 1 if (dp.get(root) == null && parent == null) { ans++; return 1; } // If the current node is unvisited // but it is not the root node if (dp.get(root) == null) return 1; // If the current node is also visited } // If there are unvisited child nodes else { // Mark the current node, // parent node and child // nodes as visited if (root.left != null) dp.put(root.left, 1); if (root.right != null) dp.put(root.right, 1); dp.put(root, 1); if (parent != null) dp.put(parent, 1); // Return 0 as now we have marked // all nodes as visited } return 0; } // Function to find required vaccines static void supplyVaccine(Node root) { dp = new HashMap<>(); ans = 0; // Passing parent of root // node as null to identify it solve(root, root); } // Driver Code public static void main(String[] args) { String treeString; Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.right = new Node(4); root.right.right.right = new Node(5); root.right.right.right.right = new Node(6); // Function call supplyVaccine(root); System.out.print(ans + "\n"); }}// This code is contributed by shikhasingrajput |
Python3
# Python code to implement the approach# Structure of a tree nodeclass Node: def __init__(self, val): self.data = val self.left = None self.right = Nonedp = {}ans = 0# Function to implement the dpdef solve(root, parent): global dp global ans # Base Condition if (root == None): return 0 # Counter Variable to store the number # of unvisited child elements for # the current node ans = solve(root.left, root) ans += solve(root.right, root) # If there are no unvisited child nodes if (ans == 0): # If the current node is root # node and unvisited increment # the answer by 1 if (root not in dp and parent == None): ans += 1 return 1 # If the current node is unvisited # but it is not the root node if (root not in dp): return 1 # If the current node is also visited # If there are unvisited child nodes else: # Mark the current node, # parent node and child # nodes as visited if (root.left != None): dp[root.left] = 1 if (root.right != None): dp[root.right] = 1 dp[root] = 1 if (parent != None): dp[parent] = 1 # Return 0 as now we have marked # all nodes as visited return 0# Function to find required vaccinesdef supplyVaccine(root): global ans # Passing parent of root # node as None to identify it solve(root, root)# Driver Coderoot = Node(1)root.left = Node(2)root.right = Node(3)root.right.right = Node(4)root.right.right.right = Node(5)root.right.right.right.right = Node(6)# Function callsupplyVaccine(root)print(ans)# This code is contributed by shinjanpatra |
C#
//C# program to implement the approachusing System;using System.Collections.Generic;public class GFG{ // Structure of a tree node class Node { public int data; public Node left; public Node right; public Node(int val){ this.data=val; this.left=this.right=null; } } static int ans; static Dictionary<Node, int> dp; // Function to implement the dp static int solve(Node root, Node parent) { // Base Condition if (root == null) return 0; // Counter Variable to store the number // of unvisited child elements for // the current node ans = solve(root.left, root); ans += solve(root.right, root); // If there are no unvisited child nodes if (ans == 0) { // If the current node is root // node and unvisited increment // the answer by 1 if (!dp.ContainsKey(root) && parent == null) { ans++; return 1; } // If the current node is unvisited // but it is not the root node if (!dp.ContainsKey(root)) return 1; // If the current node is also visited } // If there are unvisited child nodes else { // Mark the current node, // parent node and child // nodes as visited if (root.left != null) dp[root.left]=1; if (root.right != null) dp[root.right]=1; dp[root]=1; if (parent != null) dp[parent]=1; // Return 0 as now we have marked // all nodes as visited } return 0; } // Function to find required vaccines static void supplyVaccine(Node root) { dp = new Dictionary<Node,int>(); ans = 0; // Passing parent of root // node as null to identify it solve(root, root); } //Driver Code static public void Main (){ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.right = new Node(4); root.right.right.right = new Node(5); root.right.right.right.right = new Node(6); // Function call supplyVaccine(root); Console.Write(ans); }}// This code is contributed by shruti456rawal |
Javascript
<script>// javascript code to implement the approach // Structure of a tree node class Node { constructor(val) { this.data = val; this.left = this.right = null; }} var ans; var dp = new Map(); // Function to implement the dp function solve(root, parent) { // Base Condition if (root == null) return 0; // Counter Variable to store the number // of unvisited child elements for // the current node ans = solve(root.left, root); ans += solve(root.right, root); // If there are no unvisited child nodes if (ans == 0) { // If the current node is root // node and unvisited increment // the answer by 1 if (dp.get(root) == null && parent == null) { ans++; return 1; } // If the current node is unvisited // but it is not the root node if (dp.get(root) == null) return 1; // If the current node is also visited } // If there are unvisited child nodes else { // Mark the current node, // parent node and child // nodes as visited if (root.left != null) dp.set(root.left, 1); if (root.right != null) dp.set(root.right, 1); dp.set(root, 1); if (parent != null) dp.set(parent, 1); // Return 0 as now we have marked // all nodes as visited } return 0; } // Function to find required vaccines function supplyVaccine(root) { ans = 0; // Passing parent of root // node as null to identify it solve(root, root); } // Driver Code var root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.right.right = new Node(4); root.right.right.right = new Node(5); root.right.right.right.right = new Node(6); // Function call supplyVaccine(root); document.write(ans + "\n");// This code contributed by shikhasingrajput</script> |
Output
2
Time Complexity: O(N).
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
