This paper describes a frequency table-based decision tree algorithm for embedded applications. The table contains a compact statistical representation of the training set feature vectors and can be used in conjunction with a variety of learning methods. The use of the table allows a priori knowledge of the memory requirement and reduces the time for incremental tree generation by a factor of at least 10. The paper illustrates the method with an example of incremental decision tree learning applied to robot navigation. The performance of the method is compared with that of an existing incremental decision tree algorithm