A decision tree can be constructed via frequent predictive itemsets and best item splits. A hierarchical frequent predictive itemsets tree data structure can be used to construct the decision tree. A bottom-up traversal of the data structure can be used during determination of best item splits. The described technologies can construct decision trees with superior accuracy as compared to conventional greedy decision tree construction approaches.