Supervised machine learning is an approach where an algorithm estimates a mapping function by using labeled data i.e. utilizing data attributes and target values. One of the major obstacles in supervised learning is the labeling step. Obtaining labeled data is an expensive procedure since it typically requires human effort. Training a model with too little data tends to overfit therefore in order to achieve a reasonable accuracy of prediction we need a minimum number of labeled examples. This is also true for streaming machine learning models. Maintaining a model without rebuilding and performing a prediction task without ever storing input samples are the key concepts of streaming machine learning models. A successful and widely used streaming model is the Hoeffding tree which has large labeling complexity. In this work, we present Frugal Hoeffding tree, a variation of the Hoeffding tree that uses less labeled data, and provides similar performance as the original Hoeffding tree. We conduct experiments on large real-world datasets where we compare the performances of traditional batch decision trees, the Hoeffding tree and the Frugal Hoeffding tree. We show that the Frugal Hoeffding tree consumes less labeled data yet can achieve classification performance similar to the Hoeffding tree.