Maximum average of subtree values in a given Binary Tree | Structure of the Tree node ; Stores the result ; Function for finding maximum subtree average ; Checks if current node is not None and doesn 't have any children ; Stores sum of its subtree in index 0 and count number of nodes in index 1 ; Traverse all children of the current node ; Recursively calculate max average of subtrees among its children ; Increment sum by sum of its child 's subtree ; Increment number of nodes by its child 's node ; Increment sum by current node 's value ; Increment number of nodes by one ; Take maximum of ans and current node 's average ; Finally return pair of { sum , count } ; Driver Code ; Given tree ; Function call ; Print answer
class TreeNode : NEW_LINE INDENT def __init__ ( self , val ) : NEW_LINE INDENT self . val = val NEW_LINE self . children = [ ] NEW_LINE DEDENT DEDENT ans = 0.0 NEW_LINE def MaxAverage ( root ) : NEW_LINE INDENT global ans NEW_LINE if ( root != None and len ( root . children ) == 0 ) : NEW_LINE INDENT ans = max ( ans , ( root . val ) ) NEW_LINE return [ root . val , 1 ] NEW_LINE DEDENT childResult = [ 0 for i in range ( 2 ) ] NEW_LINE for child in root . children : NEW_LINE INDENT childTotal = MaxAverage ( child ) NEW_LINE childResult [ 0 ] = childResult [ 0 ] + childTotal [ 0 ] NEW_LINE childResult [ 1 ] = childResult [ 1 ] + childTotal [ 1 ] NEW_LINE DEDENT sum = childResult [ 0 ] + root . val NEW_LINE count = childResult [ 1 ] + 1 NEW_LINE ans = max ( ans , sum / count ) NEW_LINE return [ sum , count ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = TreeNode ( 20 ) NEW_LINE left = TreeNode ( 12 ) NEW_LINE right = TreeNode ( 18 ) NEW_LINE root . children . append ( left ) NEW_LINE root . children . append ( right ) NEW_LINE left . children . append ( TreeNode ( 11 ) ) NEW_LINE left . children . append ( TreeNode ( 3 ) ) NEW_LINE right . children . append ( TreeNode ( 15 ) ) NEW_LINE right . children . append ( TreeNode ( 8 ) ) NEW_LINE MaxAverage ( root ) NEW_LINE print ( ans * 1.0 ) NEW_LINE DEDENT