Privacy-preserving Decision Tree Evaluation (PDTE) is a promising approach to private Machine-Learning-as-a-Service, enabling clients to classify their data using tree models provided by model owners while only revealing the evaluation result to clients. However, the expensive overhead of current schemes is still an obstacle in practical applications. In this work, we present OCE-PTree, an online communication efficient privacy-preserving decision tree evaluation protocol with semi-honest security in a two party outsourcing computation scenario (2PC). OCE-PTree’s main contributions are two-fold: i) We utilize the vector inner product in conjunction with additive secret sharing and mask secret sharing to achieve efficient feature selection. ii) We propose a path evaluation protocol based on one-time truth table for reducing communication costs in the online phase. Experimental results on various decision trees and datasets demonstrate the superiority of our approach over the two state-of-the-art solutions by Ma \(\textit{et al.}\) (NDSS’21) and Mostree (ACSAC’23). To be more specific, we reduce the online communication costs by upto 12 \(\times \) , and improve the online running-time by at most 2.3 \(\times \) , 1.5 \(\times \) and 1.3 \(\times \) in LAN, MAN and WAN compared to Ma \(\textit{et al.}\) Additionally, in comparison to Mostree, we reduce the online communication costs by upto 1.7 \(\times \) , and improve the online running-time by at most 25 \(\times \) in both network settings.