I understand how quad trees work on square images (by splitting the image until the section is a single colour, which is stored in the leaf node).
What happens if the image has one dimension longer that the other, you may end up with a 2x1 pixel area as the smallest sub unit, making it difficult to use quadtree division methods to store a single colour. How would you solve this issue?
You could pad the image until it is an equal and power of two size. While it may add some extra memory requirements, the increase shouldn't be that large.
The 2x1 example would be padded to a standard 2x2 and store the real size or use a special value for padded nodes so you can restore the original size.