A fast rate-distortion (R-D) optimal scheme for coding adaptive trees whose individual nodes spawn descendents forming a disjoint and complete basis cover for the space spanned by their parent nodes is presented. The scheme guarantees operation on the convex hull of the operational R-D curve and uses a fast dynamic programing pruning algorithm to markedly reduce computational complexity. Applications for this coding technique include R. Coefman et al.'s (Yale Univ., 1990) generalized multiresolution wavelet packet decomposition, iterative subband coders, and quadtree structures. Applications to image processing involving wavelet packets as well as discrete cosine transform (DCT) quadtrees are presented