In this paper, a novel weighted graph based decision tree optimization algorithm is proposed. The graph is a compact representation of most possible solutions for the decision tree based classifications. The optimal decision tree is then be extracted from it using the Nlevel prediction technique. The prediction technique can incorporate future knowledge about classifications based on the tree and make the current decision on the best question more accurate when tree splitting. Tied triphones based on this method are more accurate than those using popular tree growing method from a point view of maximum likelihood. This approach provides a flexible structure to optimize the decision tree. Our experimental results show that higher performance is obtained with different level predictions.