text: d | JavaScript 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 ; Initialising the DP array ; Constructing the tree
code: let N = 1005 ; class Node { constructor ( data ) { this . left = null ; this . right = null ; this . data = data ; } } function newNode ( data ) { let node = new Node ( data ) ; return node ; } let dp = new Array ( N ) ; function minDominatingSet ( root , covered , 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 ) ) ; } 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 ) ) ; } dp [ root . data ] [ covered ] [ compulsory ] = ans ; return dp [ root . data ] [ covered ] [ compulsory ] ; } 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 ; } } 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 ) ) ;