Find maximum GCD value from root to leaf in a Binary tree | Initialise to update the maximum gcd value from all the path ; Node structure ; Initialize constructor ; Function to find gcd of a and b ; Function to find the gcd of a path ; Function to find the maximum value of gcd from root to leaf in a Binary tree ; Check if root is not null ; Find the maximum gcd of path value and store in global maxm variable ; Traverse left of binary tree ; Traverse right of the binary tree ; Driver Code ; Given Tree ; Function call ; Print the maximum AND value
global maxm NEW_LINE 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 gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def find_gcd ( arr ) : NEW_LINE INDENT if ( len ( arr ) == 1 ) : NEW_LINE INDENT return arr [ 0 ] NEW_LINE DEDENT g = arr [ 0 ] NEW_LINE for i in range ( 1 , len ( arr ) ) : NEW_LINE INDENT g = gcd ( g , arr [ i ] ) NEW_LINE DEDENT return g NEW_LINE DEDENT def maxm_gcd ( 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 . append ( root . val ) NEW_LINE maxm = max ( find_gcd ( ans ) , maxm ) NEW_LINE return NEW_LINE DEDENT ans . append ( root . val ) NEW_LINE maxm_gcd ( root . left , ans ) NEW_LINE maxm_gcd ( root . right , ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( 15 ) NEW_LINE root . left = Node ( 3 ) NEW_LINE root . right = Node ( 7 ) NEW_LINE root . left . left = Node ( 15 ) NEW_LINE root . left . right = Node ( 1 ) NEW_LINE root . right . left = Node ( 31 ) NEW_LINE root . right . right = Node ( 9 ) NEW_LINE maxm_gcd ( root , [ ] ) NEW_LINE print ( maxm ) NEW_LINE DEDENT