Bayesian Decision Trees (DTs) are strong probabilistic models that integrate observed data with prior beliefs, providing robust interpretability in Machine Learning uncertainty. They are highly valuable in several fields such as Medicine, Finance and Education because of their ability to balance generalization and adaptability. However, tuning the Poisson prior parameter \(\lambda \) , which controls the expected number of leaf nodes, is crucial as a poor choice can lead to inefficient sampling, suboptimal posterior approximations, and increased computational cost. In this work, we propose a novel Recursive Interval Optimization (RIO) algorithm that, with high probability, preserves the most promising interval at each subdivision and has quasi-polynomial computational complexity in the interval width under mild assumptions. Furthermore, we experimentally demonstrate that RIO-tuned SMC on multiple real-world classification datasets outperforms traditional Random Search (RS) and standard Random Forest (RF) in accuracy while producing more compact trees. These results highlight RIO’s effectiveness and theoretical guarantees for hyperparameter tuning of Bayesian DTs.