Service Oriented Architecture (SOA) has become a new software development paradigm because it provides a flexible framework that can help reduce development cost and time. SOA also promises loosely coupled, interoperable, and composable services. In order to maximize these benefits, many researchers have focused on service composition techniques, especially in terms of providing quality of services (QoS) to consumers in a dynamic environment. In current literature, many approaches, such as the Genetic Algorithm, Integer Programming, and the Pinsinger Algorithm approaches, have been proposed for service compositions to provide quality of services to consumers. However, these approaches are inefficient when any problem occurs during service executions since the problem causes the current execution stop, and service rebinding is required for the unexecuted path. In addition, even if a better service is discovered, it cannot be easily replaced in these approaches because replacing a single service causes a problem on global QoS constraints. In this paper, we focus on these problems by proposing a tree-based algorithm in order to provide optimal services to consumers consistently and efficiently even when the status of selected services have changed. As a result, consumers can always use the optimal services of high qualities.