text: d | C # program to find the size of the minimum dominating set of the tree ; Definition of a tree node ; Helper function that allocates a new node ; DP array to precompute and store the results ; minDominatingSettion to return the size of the minimum dominating set of the array ; Base case ; Setting the compulsory value if needed ; Check if the answer is already computed ; If it is compulsory to select the node ; Choose the node and set its children as covered ; If it is covered ; If the current node is neither covered nor needs to be selected compulsorily ; Store the result ; Driver code ; Initialising the DP array ; Constructing the tree
code: using System ; class GFG { static readonly int N = 1005 ; public class Node { public int data ; public Node left , right ; } ; public static Node newNode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = node . right = null ; return node ; } static int [ , , ] dp = new int [ N , 5 , 5 ] ; static int minDominatingSet ( Node root , int covered , int compulsory ) { if ( root == null ) return 0 ; if ( root . left != null && root . right != null && covered > 0 ) compulsory = 1 ; if ( dp [ root . data , covered , compulsory ] != - 1 ) return dp [ root . data , covered , compulsory ] ; if ( compulsory > 0 ) { return dp [ root . data , covered , compulsory ] = 1 + minDominatingSet ( root . left , 1 , 0 ) + minDominatingSet ( root . right , 1 , 0 ) ; } 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 ) ) ; } 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 ) ) ; } return dp [ root . data , covered , compulsory ] = ans ; } public static void Main ( String [ ] args ) { 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 ; } } 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 ) + " STRNEWLINE " ) ; } }