Orthogonal least-squares (OLS) regression with tunable kernels has been recently introduced, in which a greedy scheme is utilized to tune the parameters of each individual regressor term by term using a global search algorithm. To improve the performance of the greedy-scheme-based OLS algorithm, a tree structure search algorithm is constructed. At each regressor stage, this proposed OLS algorithm is realized by keeping multiple best regressors rather than using the optimal one only. Numerical results show that this new scheme is capable of producing a much sparser regression model with better generalization than the conventional approaches.