Given a binary tree with N nodes numbered [1, N], the task is to find the size of the smallest Dominating set of that tree.
A set of nodes is said to be a dominating node if every node in the binary tree not present in the set is an immediate child/parent to any node in that set.
Examples:
Input:
1
/
2
/ \
4 3
/
5
/ \
6 7
/ \ \
8 9 10
Output: 3
Explanation:
Smallest dominating set is {2, 6, 7}
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
Output: 4
Explanation:
One of the smallest
dominating set = {2, 3, 6, 4}
Approach:Â
In order to solve this problem we are using a dynamic programming approach by defining the following two states for every node:
- The first state compulsory tells us whether it is compulsory to choose the node in the set or not.
- The second state covered, tells us whether the node’s parent/child is in the set or not.
If it is compulsory to choose the node, we choose it and mark its children as covered. Otherwise, we have an option to choose it or reject it and then update its children as covered or not accordingly. Check the states for every node and find the required size of the set accordingly.
Below code is the implementation of the above approach:
C++
/* C++ program to find the size of theminimum dominating set of the tree */Â
#include <bits/stdc++.h>using namespace std;Â
#define N 1005Â
// Definition of a tree nodestruct Node {Â Â Â Â int data;Â Â Â Â Node *left, *right;};Â
/* Helper function that allocates a new node */Node* newNode(int data){Â Â Â Â Node* node = new Node();Â Â Â Â node->data = data;Â Â Â Â node->left = node->right = NULL;Â Â Â Â return node;}Â
// DP array to precompute// and store the resultsint dp[N][5][5];Â
// minDominatingSettion to return the size of// the minimum dominating set of the arrayint minDominatingSet(Node* root, int covered,                     int compulsory){    // Base case    if (!root)        return 0;Â
    // Setting the compulsory value if needed    if (!root->left and !root->right and !covered)        compulsory = true;Â
    // Check if the answer is already computed    if (dp[root->data][covered][compulsory] != -1)        return dp[root->data][covered][compulsory];Â
    // If it is compulsory to select    // the node    if (compulsory) {        // Choose the node and set its children as covered        return dp[root->data]                 [covered]                 [compulsory]               = 1                 + minDominatingSet(                       root->left, 1, 0)                 + minDominatingSet(                       root->right, 1, 0);    }Â
    // If it is covered    if (covered) {        return dp[root->data]                 [covered]                 [compulsory]               = min(                   1                       + minDominatingSet(                             root->left, 1, 0)                       + minDominatingSet(                             root->right, 1, 0),                   minDominatingSet(                       root->left, 0, 0)                       + minDominatingSet(                             root->right, 0, 0));    }Â
    // If the current node is neither covered nor    // needs to be selected compulsorily    int ans = 1              + minDominatingSet(                    root->left, 1, 0)              + minDominatingSet(                    root->right, 1, 0);Â
    if (root->left) {        ans = min(ans,                  minDominatingSet(                      root->left, 0, 1)                      + minDominatingSet(                            root->right, 0, 0));    }    if (root->right) {        ans = min(ans,                  minDominatingSet(                      root->left, 0, 0)                      + minDominatingSet(                            root->right, 0, 1));    }Â
    // Store the result    return dp[root->data]             [covered]             [compulsory]           = ans;}Â
// Driver codesigned main(){    // initialising the DP array    memset(dp, -1, sizeof(dp));Â
    // Constructing the tree    Node* root = newNode(1);    root->left = newNode(2);    root->left->left = newNode(3);    root->left->right = newNode(4);    root->left->left->left = newNode(5);    root->left->left->left->left = newNode(6);    root->left->left->left->right = newNode(7);    root->left->left->left->right->right = newNode(10);    root->left->left->left->left->left = newNode(8);    root->left->left->left->left->right = newNode(9);Â
    cout << minDominatingSet(root, 0, 0) << endl;Â
    return 0;} |
Java
// Java program to find the size of the//minimum dominating set of the tree import java.util.*;Â
class GFG{Â
static final int N = 1005;Â
// Definition of a tree nodestatic class Node{Â Â Â Â int data;Â Â Â Â Node left, right;};Â
// Helper function that allocates a // new node static Node newNode(int data){Â Â Â Â Node node = new Node();Â Â Â Â node.data = data;Â Â Â Â node.left = node.right = null;Â Â Â Â return node;}Â
// DP array to precompute// and store the resultsstatic int [][][]dp = new int[N][5][5];Â
// minDominatingSettion to return the size of// the minimum dominating set of the arraystatic int minDominatingSet(Node root,                             int covered,                            int compulsory){    // Base case    if (root == null)        return 0;         // Setting the compulsory value if needed    if (root.left != null &&        root.right != null &&       covered > 0)        compulsory = 1;Â
    // Check if the answer is already computed    if (dp[root.data][covered][compulsory] != -1)        return dp[root.data][covered][compulsory];Â
    // If it is compulsory to select    // the node    if (compulsory > 0)    {                 // Choose the node and set its        // children as covered        return dp[root.data][covered][compulsory] = 1 +                 minDominatingSet(root.left, 1, 0) +                 minDominatingSet(root.right, 1, 0);    }Â
    // If it is covered    if (covered > 0)    {        return dp[root.data][covered]                 [compulsory] = Math.min(1 +                   minDominatingSet(root.left, 1, 0) +                   minDominatingSet(root.right, 1, 0),                  minDominatingSet(root.left, 0, 0)+                  minDominatingSet(root.right, 0, 0));    }Â
    // If the current node is neither covered nor    // needs to be selected compulsorily    int ans = 1 + minDominatingSet(root.left, 1, 0) +                  minDominatingSet(root.right, 1, 0);Â
    if (root.left != null)    {        ans = Math.min(ans,               minDominatingSet(root.left, 0, 1) +              minDominatingSet(root.right, 0, 0));    }    if (root.right != null)     {        ans = Math.min(ans,              minDominatingSet(root.left, 0, 0) +               minDominatingSet(root.right, 0, 1));    }Â
    // Store the result    return dp[root.data][covered][compulsory] = ans;}Â
// Driver codepublic static void main(String[] args){         // Initialising the DP array    for(int i = 0; i < N; i++)    {        for(int j = 0; j < 5; j++)        {            for(int l = 0; l < 5; l++)                dp[i][j][l] = -1;        }    }Â
    // Constructing the tree    Node root = newNode(1);    root.left = newNode(2);    root.left.left = newNode(3);    root.left.right = newNode(4);    root.left.left.left = newNode(5);    root.left.left.left.left = newNode(6);    root.left.left.left.right = newNode(7);    root.left.left.left.right.right = newNode(10);    root.left.left.left.left.left = newNode(8);    root.left.left.left.left.right = newNode(9);Â
    System.out.print(minDominatingSet(        root, 0, 0) + "\n");}}Â
// This code is contributed by amal kumar choubey |
Python3
# Python3 program to find the size of the# minimum dominating set of the tree */N = 1005  # Definition of a tree nodeclass Node:         def __init__(self, data):                 self.data = data        self.left = None        self.right = None      # Helper function that allocates a # new node def newNode(data):Â
    node = Node(data)    return node  # DP array to precompute# and store the resultsdp = [[[-1 for i in range(5)] for j in range(5)] for k in range(N)];  # minDominatingSettion to return the size of# the minimum dominating set of the arraydef minDominatingSet(root, covered, compulsory):Â
    # Base case    if (not root):        return 0;      # Setting the compulsory value if needed    if (not root.left and not root.right and not covered):        compulsory = True;      # Check if the answer is already computed    if (dp[root.data][covered][compulsory] != -1):        return dp[root.data][covered][compulsory];      # If it is compulsory to select    # the node    if (compulsory):                 dp[root.data][covered][compulsory] = 1 + minDominatingSet(root.left, 1, 0) + minDominatingSet(root.right, 1, 0);                 # Choose the node and set its children as covered        return dp[root.data][covered][compulsory]          # If it is covered    if (covered):        dp[root.data][covered][compulsory] = min(1 + minDominatingSet(root.left, 1, 0) + minDominatingSet(root.right, 1, 0),minDominatingSet(root.left, 0, 0)+ minDominatingSet(root.right, 0, 0));        return dp[root.data][covered][compulsory]          # If the current node is neither covered nor    # needs to be selected compulsorily    ans = 1 + minDominatingSet(root.left, 1, 0) + minDominatingSet(root.right, 1, 0);      if (root.left):        ans = min(ans, minDominatingSet(root.left, 0, 1) + minDominatingSet(root.right, 0, 0));         if (root.right):        ans = min(ans, minDominatingSet( root.left, 0, 0) + minDominatingSet(root.right, 0, 1));          # Store the result    dp[root.data][covered][compulsory]= ans;    return ansÂ
# Driver codeif __name__=='__main__':          # Constructing the tree    root = newNode(1);    root.left = newNode(2);    root.left.left = newNode(3);    root.left.right = newNode(4);    root.left.left.left = newNode(5);    root.left.left.left.left = newNode(6);    root.left.left.left.right = newNode(7);    root.left.left.left.right.right = newNode(10);    root.left.left.left.left.left = newNode(8);    root.left.left.left.left.right = newNode(9);      print(minDominatingSet(root, 0, 0))     # This code is contributed by rutvik_56 |
C#
// C# program to find the size of the//minimum dominating set of the tree using System;class GFG{Â
static readonly int N = 1005;Â
// Definition of a tree nodepublic class Node{    public int data;    public Node left, right;};Â
// Helper function that allocates a // new node public static Node newNode(int data){Â Â Â Â Node node = new Node();Â Â Â Â node.data = data;Â Â Â Â node.left = node.right = null;Â Â Â Â return node;}Â
// DP array to precompute// and store the resultsstatic int [,,]dp = new int[N, 5, 5];Â
// minDominatingSettion to return the size of// the minimum dominating set of the arraystatic int minDominatingSet(Node root,                             int covered,                            int compulsory){    // Base case    if (root == null)        return 0;         // Setting the compulsory value if needed    if (root.left != null &&        root.right != null &&       covered > 0)        compulsory = 1;Â
    // Check if the answer is already computed    if (dp[root.data, covered, compulsory] != -1)        return dp[root.data, covered, compulsory];Â
    // If it is compulsory to select    // the node    if (compulsory > 0)    {                 // Choose the node and set its        // children as covered        return dp[root.data, covered, compulsory] = 1 +                    minDominatingSet(root.left, 1, 0) +                   minDominatingSet(root.right, 1, 0);    }Â
    // If it is covered    if (covered > 0)    {        return dp[root.data, covered, compulsory] = Math.Min(1 +                              minDominatingSet(root.left, 1, 0) +                              minDominatingSet(root.right, 1, 0),                             minDominatingSet(root.left, 0, 0)+                            minDominatingSet(root.right, 0, 0));    }Â
    // If the current node is neither covered nor    // needs to be selected compulsorily    int ans = 1 + minDominatingSet(root.left, 1, 0) +                  minDominatingSet(root.right, 1, 0);Â
    if (root.left != null)    {        ans = Math.Min(ans,               minDominatingSet(root.left, 0, 1) +              minDominatingSet(root.right, 0, 0));    }    if (root.right != null)     {        ans = Math.Min(ans,              minDominatingSet(root.left, 0, 0) +               minDominatingSet(root.right, 0, 1));    }Â
    // Store the result    return dp[root.data, covered, compulsory] = ans;}Â
// Driver codepublic static void Main(String[] args){         // Initialising the DP array    for(int i = 0; i < N; i++)    {        for(int j = 0; j < 5; j++)        {            for(int l = 0; l < 5; l++)                dp[i, j, l] = -1;        }    }Â
    // Constructing the tree    Node root = newNode(1);    root.left = newNode(2);    root.left.left = newNode(3);    root.left.right = newNode(4);    root.left.left.left = newNode(5);    root.left.left.left.left = newNode(6);    root.left.left.left.right = newNode(7);    root.left.left.left.right.right = newNode(10);    root.left.left.left.left.left = newNode(8);    root.left.left.left.left.right = newNode(9);Â
    Console.Write(minDominatingSet                  root, 0, 0) + "\n");}}Â
// This code is contributed by Rohit_ranjan |
Javascript
<script>Â
    // JavaScript program to find the size of the    //minimum dominating set of the tree         let N = 1005;      // Definition of a tree node    class Node    {       constructor(data) {           this.left = null;           this.right = null;           this.data = data;        }    }         // Helper function that allocates a    // new node    function newNode(data)    {        let node = new Node(data);        return node;    }Â
    // DP array to precompute    // and store the results    let dp = new Array(N);Â
    // minDominatingSettion to return the size of    // the minimum dominating set of the array    function minDominatingSet(root, covered, compulsory)    {        // Base case        if (root == null)            return 0;Â
        // Setting the compulsory value if needed        if (root.left != null &&           root.right != null &&           covered > 0)            compulsory = 1;Â
        // Check if the answer is already computed        if (dp[root.data][covered][compulsory] != -1)            return dp[root.data][covered][compulsory];Â
        // If it is compulsory to select        // the node        if (compulsory > 0)        {Â
            // Choose the node and set its            // children as covered            return dp[root.data][covered][compulsory] = 1 +                     minDominatingSet(root.left, 1, 0) +                     minDominatingSet(root.right, 1, 0);        }Â
        // If it is covered        if (covered > 0)        {            return dp[root.data][covered]                     [compulsory] = Math.min(1 +                      minDominatingSet(root.left, 1, 0) +                      minDominatingSet(root.right, 1, 0),                      minDominatingSet(root.left, 0, 0)+                      minDominatingSet(root.right, 0, 0));        }Â
        // If the current node is neither covered nor        // needs to be selected compulsorily        let ans = 1 + minDominatingSet(root.left, 1, 0) +                      minDominatingSet(root.right, 1, 0);Â
        if (root.left != null)        {            ans = Math.min(ans,                  minDominatingSet(root.left, 0, 1) +                  minDominatingSet(root.right, 0, 0));        }        if (root.right != null)        {            ans = Math.min(ans,                  minDominatingSet(root.left, 0, 0) +                  minDominatingSet(root.right, 0, 1));        }Â
        // Store the result        dp[root.data][covered][compulsory] = ans;        return dp[root.data][covered][compulsory];    }         // Initialising the DP array    for(let i = 0; i < N; i++)    {        dp[i] = new Array(5);        for(let j = 0; j < 5; j++)        {            dp[i][j] = new Array(5);            for(let l = 0; l < 5; l++)                dp[i][j][l] = -1;        }    }      // Constructing the tree    let root = newNode(1);    root.left = newNode(2);    root.left.left = newNode(3);    root.left.right = newNode(4);    root.left.left.left = newNode(5);    root.left.left.left.left = newNode(6);    root.left.left.left.right = newNode(7);    root.left.left.left.right.right = newNode(10);    root.left.left.left.left.left = newNode(8);    root.left.left.left.left.right = newNode(9);      document.write(minDominatingSet(root, 0, 0));             </script> |
Output:Â
3
Â
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!
