Bayesian Optimization (BO) frameworks typically assume the function to be optimized is stationary (homogeneous) over the domain. However, in many real-world applications, we often deal with functions that present a rate of variation across the input space. In this paper, we optimize functions where a finite set of homogeneous functions defined over partitions of the input space can represent the heterogeneity. The disconnected partitions that can be characterized by the same function are said to be in the same class, and evaluating the function at input returns the minimum distance to a boundary of the contiguous class (partition). The ClassGP modeling framework, previously developed to model for such heterogenous functions along with a novel ClassUCB acquisition function and partition sampling strategy, is used to introduce a novel tree-based optimization framework dubbed as ClassBO (Class Bayesian Optimization). We demonstrate the superior performance of ClassBO against other methods via empirical evaluations.