checker board and floyd? steinberg? error diffusion tell me that you have to take more neighbors into account. Bilinear filtering for textures. When that works, apply on tree, top down.
From an image processing standpoint you should be able to use a gradient technique. https://en.wikipedia.org/wiki/Image_gradient I'd use a 3x3 kernel to start with and maybe combine a larger kernel to generate a gradient map. Post process the gradient to smooth it then apply the changes to the grayscale image. Using this you can even increase the resolution.
One nice thing about smoothing is that there is most often a solution. Even if it is not fully isotropic, most user will not notice. Do not let the tree confuse you. If you have time, play and train with the grid examples. Try to reuse this code for the tree.
Anyway I do not know why to quad-tree compress anyways. Is this for a sky with stars?
Could just go with spherical guassians: http://blog.selfshadow.com/publications/s2015-shading-course/rad/s2015_pbs_rad_slides.pdf
Same exact purpose and idea as SH, but has better angular resolution and less artifacts.
