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 ; A utility function to create a node ; Let us construct the tree given in the above diagram
def max ( x , y ) : NEW_LINE INDENT if ( x > y ) : NEW_LINE INDENT return x NEW_LINE DEDENT else : NEW_LINE INDENT return y NEW_LINE DEDENT DEDENT class node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def LISS ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT size_excl = LISS ( root . left ) + LISS ( root . right ) NEW_LINE size_incl = 1 NEW_LINE if ( root . left != None ) : NEW_LINE INDENT size_incl += LISS ( root . left . left ) + LISS ( root . left . right ) NEW_LINE DEDENT if ( root . right != None ) : NEW_LINE INDENT size_incl += LISS ( root . right . left ) + LISS ( root . right . right ) NEW_LINE DEDENT return max ( size_incl , size_excl ) NEW_LINE DEDENT def newNode ( data ) : NEW_LINE INDENT temp = node ( ) NEW_LINE temp . data = data NEW_LINE temp . left = temp . right = None NEW_LINE return temp NEW_LINE DEDENT root = newNode ( 20 ) NEW_LINE root . left = newNode ( 8 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 12 ) NEW_LINE root . left . right . left = newNode ( 10 ) NEW_LINE root . left . right . right = newNode ( 14 ) NEW_LINE root . right = newNode ( 22 ) NEW_LINE root . right . right = newNode ( 25 ) NEW_LINE print ( " Size ▁ of ▁ the ▁ Largest " , " ▁ Independent ▁ Set ▁ is ▁ " , LISS ( root ) ) NEW_LINE