Binary tree predictive coding (BTPC) is an efficient general-purpose still-image compression scheme, competitive with JPEG for natural image coding and with GIF for graphics. We report the extension of BTPC to video compression using motion estimation and compensation techniques which are simple, efficient, nonlinear and predictive. The new methods, binary tree recursive motion estimation coding (BTRMEC), and binary tree residue coding (BTRC) exploit the hierarchical structure of BTPC, in the first case giving progressively refined motion estimates for increasing numbers of pels and in the second case providing efficient residue coding. Compression results for BTRMEC and BTBC are compared against conventional block-based motion compensated coding as provided by MPEG. They show that both BTRMEC and BTRC are efficient methods to code video sequences.