I would try something along the lines of
int find_max_data_size( Node * p ) {
if( !p ) return 0;
int const left_size = find_max_data_size( p->left );
int const right_size = find_max_data_size( p->right );
int const my_size = get_size( p->data );
return max( left_size, right_size, my_size );
}
and call find_max_data_size( root )
;