In this paper, we propose an enhancement of the Tree-based authentication protocol, named as the Tree-LSHB+ protocol. The protocol is a lightweight authentication protocol that is suitable for use in radio frequency identification (RFID) systems. Compared with the Tree-based HB authentication protocol, our protocol provides mutual authentication in authentication stage. The authentication keys stored in the reader and the tag are also updated when the mutual authentication succeeds. It means that two drawbacks can be avoided in the Tree-based authentication protocol, one is that only the reader authenticates the tag and the other is that the secret keys stored in the tags remain unchanged all the time. We also improve the performance of Tree-based protocol with the property of Toeplitz matrix and find that the Tree-LSHB+ protocol is still a good choice for RFID authentication.