The 2016 safety Final Rule requires states to have access to annual average daily traffic (AADT) for all public paved roads, including non-Federal aid-system (NFAS) roads. The latter account approximately for 75% of the total roadway mileage in the country making it difficult for agencies to collect traffic data on these roads. Many agencies use stratified sampling procedures to develop default AADT estimates for uncounted segments; however, there is limited guidance and information about how to stratify the network effectively. The goal of this paper is to enhance transportation agencies ability to improve existing stratification schemes, design new schemes, and ultimately develop more accurate AADT estimates for NFAS roads. The paper presents the results from five pilot studies that validated and compared the performance of current, updated, and new (traditional and decision-tree-based) schemes using readily available data. According to the results, the median absolute percent error of existing AADT estimates, developed by state agencies, ranged between 71% and 120%. Updating these schemes using recent counts resulted in an AADT accuracy improvement of 25%. The best-performing schemes were developed using DTs that improved the AADT accuracy of existing schemes by 41%. Overall, having more strata and very homogenous strata is better than having fewer strata and more samples within each stratum. The analysis revealed that a key to selecting an effective scheme is to determine a critical point, beyond which creating more strata improves the AADT accuracy marginally but increases the required sample size exponentially.