Largest Independent Set Problem | DP | A utility function to find max of two integers ; A binary tree node has data , pointer to left child and a pointer to right child ; The function returns size of the largest independent set in a given binary tree ; Calculate size excluding the current node ; Calculate size including the current node ; Return the maximum of two sizes ; Let us construct the tree given in the above diagram
function max ( x , y ) { return ( x > y ) ? x : y ; } class Node { constructor ( data ) { this . data = data ; this . left = this . right = null ; } } function LISS ( root ) { if ( root == null ) return 0 ; let size_excl = LISS ( root . left ) + LISS ( root . right ) ; let size_incl = 1 ; if ( root . left != null ) size_incl += LISS ( root . left . left ) + LISS ( root . left . right ) ; if ( root . right != null ) size_incl += LISS ( root . right . left ) + LISS ( root . right . right ) ; return max ( size_incl , size_excl ) ; } let root = new Node ( 20 ) ; root . left = new Node ( 8 ) ; root . left . left = new Node ( 4 ) ; root . left . right = new Node ( 12 ) ; root . left . right . left = new Node ( 10 ) ; root . left . right . right = new Node ( 14 ) ; root . right = new Node ( 22 ) ; root . right . right = new Node ( 25 ) ; document . write ( " " + " " + LISS ( root ) ) ;