You don't need quadtrees for this. If you're not used to recursion, I would suggest an RLE approach like Minecraft uses, because it's simpler to understand: for every vertical column of pixels, store ranges saying where that column starts and ends, in vertical pixel coordinates. Multiple ranges then allow for multiply-fragmented terrain, or what is known in voxel lingo as "overhangs". For example:
Assuming your space is 256 units high, this means this entire column is solid ground, from end to end. Other columns nearby might not be, such as:
which is a column that's been fragmented. We have a solid volume from the "sea level"
115, then there is a space of air between
121, then we have another solid range from
121-167, another air space, then we conclude the solid from
170 to the max height of
Why use only values
0-255? Because that's the range a single 8-bit byte can support, making transfer of such information cheaper (across system bus, across network, etc.). You could also go for unsigned
int, @ 16 bits with range up to
0-16384. Bytes and shorts also make more efficient use of limited CPU cache / line space, meaning you can increase CPU throughput.
Your world consists of these columns, each of which are made up of the ranges described above.
List<RLEColumn> columns; //running left to right
byte min; //unsigned
byte max; //unsigned
or maybe, if you're willing to limit the amount of vertical fragmentation to make it more efficient:
Range ranges; //could make this length 4, 8, 16 or what have you