This paper revisits an adaptation of the random forest algorithm for Fréchet regression, addressing the challenge of regression in the context of random objects in metric spaces. Recognizing the limitations of previous approaches, we introduce a new splitting rule that circumvents the computationally expensive operation of Fréchet means by substituting with a medoid-based approach. We validate this approach by demonstrating its asymptotic equivalence to Fréchet mean-based procedures and establish the consistency of the associated regression estimator. The paper provides a sound theoretical framework and a more efficient computational approach to Fréchet regression, broadening its application to non-standard data types and complex use cases.