As machine learning (ML) systems are increasingly used in various fields, including tasks with high social impact, concerns about their fairness are growing. To address these concerns, individual fairness testing (IFT) has been introduced to identify individual discriminatory instances (IDIs) that indicate the violation of individual fairness in a given ML classifier. In this paper, we propose a black-box testing algorithm for IFT, named Aft (short for Approximation-guided Fairness Testing). Aft constructs approximate models based on decision trees, and generates test cases by sampling paths of the decision trees. Our evaluation by experiments confirms that Aft outperforms the state-of-the-art black-box IFT algorithm ExpGA both in efficiency (by 3.42 times) and diversity of IDIs identified by algorithms (by 1.16 times).