Maximum average of subtree values in a given Binary Tree | C ++ program for the above approach ; Structure of the Tree node ; Stores the result ; Function for finding maximum subtree average ; Checks if current node is not NULL 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TreeNode { int val ; vector < TreeNode * > children ; TreeNode ( int v ) { val = v ; } } ; double ans = 0.0 ; vector < int > MaxAverage ( TreeNode * root ) { if ( root != NULL && root -> children . size ( ) == 0 ) { ans = max ( ans , ( root -> val ) * ( 1.0 ) ) ; return { root -> val , 1 } ; } vector < int > childResult ( 2 ) ; for ( TreeNode * child : root -> children ) { vector < int > childTotal = MaxAverage ( child ) ; childResult [ 0 ] = childResult [ 0 ] + childTotal [ 0 ] ; childResult [ 1 ] = childResult [ 1 ] + childTotal [ 1 ] ; } int sum = childResult [ 0 ] + root -> val ; int count = childResult [ 1 ] + 1 ; ans = max ( ans , sum / count * 1.0 ) ; return { sum , count } ; } int main ( ) { TreeNode * root = new TreeNode ( 20 ) ; TreeNode * left = new TreeNode ( 12 ) ; TreeNode * right = new TreeNode ( 18 ) ; root -> children . push_back ( left ) ; root -> children . push_back ( right ) ; left -> children . push_back ( new TreeNode ( 11 ) ) ; left -> children . push_back ( new TreeNode ( 3 ) ) ; right -> children . push_back ( new TreeNode ( 15 ) ) ; right -> children . push_back ( new TreeNode ( 8 ) ) ; MaxAverage ( root ) ; printf ( " % 0.1f STRNEWLINE " , ans ) ; }