When an application code is downloaded from an unknown server to the mobile device, it is important to authenticate the code. Usually, code execution is overlapped with downloading to reduce transfer/invocation delay. In this letter, we present an efficient code authentication scheme that permits overlapping of execution and downloading when the sequence of code execution is determined during the execution time. The proposed scheme is based on authentication trees. Compared with the tree chaining scheme, the proposed scheme has lower communication overhead and shorter average verification delay. Also, the computation cost of the proposed scheme on the receiver is much smaller than that of the tree chaining scheme.