It has been suggested that codebook coding of LPC residuals offers significant performance advantage over tree coding at very low rates [cf. M. R. Schroeder and B. S. Atal, Proc. ICASSP 85]. An innovation codebook provides a better coveting of the LPC innovation space (in the sense of having a smaller covering radius) than an innovation tree of the corresponding rate. These comparisons usually assume that the branches of the innovation tree are populated with independent identically distributed random variates (i.e., a stochastic tree). In this paper, the methods of selecting the innovation elements on a binary innovation tree such that the branches contain “complementary” sequences are examined. The covering properties of these “complementary” tree codes are compared with the covering properties of stochastic trees and stochastic codebooks. The results on the “complementary” tree codes indicate that (1) the performance of an innovation code did not correlate with its covering radius and (2) tree coding of LPC residuals at very low bit rate (rate 1/4 code) did not result in any performance degradation.