Maximize count of set bits in a root to leaf path in a binary tree | Python3 program to implement the above approach ; Node class ; Initialise constructor ; Function to count the number of 1 in number ; Function to find the maximum count of setbits in a root to leaf ; Check if root is null ; Update the maximum count of setbits ; Traverse left of binary tree ; Traverse right of the binary tree ; Driver code
maxm = 0 NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . val = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def count_1 ( n ) : NEW_LINE INDENT count = 0 NEW_LINE while ( n ) : NEW_LINE INDENT count += n & 1 NEW_LINE n >>= 1 NEW_LINE DEDENT return count NEW_LINE DEDENT def maxm_setbits ( root , ans ) : NEW_LINE INDENT global maxm NEW_LINE if not root : NEW_LINE INDENT return NEW_LINE DEDENT if ( root . left == None and root . right == None ) : NEW_LINE INDENT ans += count_1 ( root . val ) NEW_LINE maxm = max ( ans , maxm ) NEW_LINE return NEW_LINE DEDENT maxm_setbits ( root . left , ans + count_1 ( root . val ) ) NEW_LINE maxm_setbits ( root . right , ans + count_1 ( root . val ) ) NEW_LINE DEDENT root = Node ( 15 ) NEW_LINE root . left = Node ( 3 ) NEW_LINE root . right = Node ( 7 ) NEW_LINE root . left . left = Node ( 5 ) NEW_LINE root . left . right = Node ( 1 ) NEW_LINE root . right . left = Node ( 31 ) NEW_LINE root . right . right = Node ( 9 ) NEW_LINE maxm_setbits ( root , 0 ) NEW_LINE print ( maxm ) NEW_LINE