text: Vertex Cover Problem | Set 2 ( Dynamic Programming Solution for Tree ) | Dynamic programming based program for Vertex Cover problem for a Binary Tree ; A utility function to find min of two integers ; A binary tree node has data , pointer to left child and a pointer to right child ; A memoization based function that returns size of the minimum vertex cover . ; The size of minimum vertex cover is zero if tree is empty or there is only one node ; If vertex cover for this node is already evaluated , then return it to save recomputation of same subproblem again . ; Calculate size of vertex cover when root is part of it ; Calculate size of vertex cover when root is not part of it ; Minimum of two values is vertex cover , store it before returning ; A utility function to create a node ; Set the vertex cover as 0 ; Driver program to test above functions ; Let us construct the tree given in the above diagram
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE int min ( int x , int y ) { return ( x < y ) ? x : y ; } struct node { int data ; int vc ; struct node * left , * right ; } ; int vCover ( struct node * root ) { if ( root == NULL ) return 0 ; if ( root -> left == NULL && root -> right == NULL ) return 0 ; if ( root -> vc != 0 ) return root -> vc ; int size_incl = 1 + vCover ( root -> left ) + vCover ( root -> right ) ; int size_excl = 0 ; if ( root -> left ) size_excl += 1 + vCover ( root -> left -> left ) + vCover ( root -> left -> right ) ; if ( root -> right ) size_excl += 1 + vCover ( root -> right -> left ) + vCover ( root -> right -> right ) ; root -> vc = min ( size_incl , size_excl ) ; return root -> vc ; } struct node * newNode ( int data ) { struct node * temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> data = data ; temp -> left = temp -> right = NULL ; temp -> vc = 0 ; return temp ; } int main ( ) { struct node * root = newNode ( 20 ) ; root -> left = newNode ( 8 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 12 ) ; root -> left -> right -> left = newNode ( 10 ) ; root -> left -> right -> right = newNode ( 14 ) ; root -> right = newNode ( 22 ) ; root -> right -> right = newNode ( 25 ) ; printf ( " Size ▁ of ▁ the ▁ smallest ▁ vertex ▁ cover ▁ is ▁ % d ▁ " , vCover ( root ) ) ; return 0 ; }