We have examined the performance of the CUBIST regression tree in filling cloud covered and/or areas affected by the Scan-Line Corrector (SLC) failure on Landsat Imagery. Tests were performed on two terrain- and atmospherically-corrected yet cloudy Landsat 5 scenes and a subset of three L7 images each acquired a month apart over the Upper Delaware River Basin. Regression tree results are within 0.5% reflectance in the visible wavelengths, between 1.5 and 2.7% for Landsat Band 4, and between 0.6 and 1.4% reflectance in Bands 5 and 7. Visual examination of the regression-filled images shows that, IF clouds and shadows in the input scenes can be accurately detected before processing of the data, regression trees are an effective tool to mitigate not only the image gaps due to the SLC failure, but also clouds and cloud shadows.