Data Structures and Algorithm

Write a code in C$++$:

A quadtree is a representation format used to encode images. The

fundamental idea behind the quadtree is that any image can be split into four quadrants. Each quadrant may again be split in four sub quadrants, etc. In the quadtree, the image is represented by a parent node, while the four quadrants are represented by four child nodes, in a predetermined order. Of course, if the whole image is a single color, it can be represented by a quadtree consisting of a single node. In general, a quadrant needs only to be subdivided if it consists of pixels of different colors. As a result, the quadtree need not be of uniform depth.

The picture below shows a quadtree of an $8$ x $8$ image. The order of quadrants is clockwise starting from top left.

Implement functions to convert between $2$D binary matrix and quadtree representations of images. Also implement a function to display the $2$D matrix representation of the image, and use it to show the original image and the image reconstructed from the quadtree form.