In lack of an analysis of the actual generation algorithm, I just went to a coral reef and made a few observations, which I'll try and form into somewhat of an analysis of the possible coral structures. But note that this is purely emprical and likely incomplete.
First of all, the structures seem to fall into three distinct general categories. They are only ever generated from a single kind of coral block, but they can of course generate into each other, forming more elaborate constructions.
Those are most similar to trees. They originate from a single vertical stem of various height (~1-3), from which branches can grow out in all 4 directions. The growth is diagonally upward in vertical segments of varying height (up to 4, rarely even 5), however, the first segment growing away from the stem seems to always be just a single block. The number of segments in each branch (and thus the diameter of the structure) can reach up to 3, rarely even 4 blocks, making the whole thing on average 5-7 blocks wide in x and z. Some of the 4 directions might be missing branches entirely, though.
Those work in a similar way of a central source block and branches going out. However, the branches go out more horizontally (though, still diagonally upwards) and into the same direction. From the central block there can be up to 3 branches (from the block itself and 1 block diagonally upwards to the left and right each) going into a common direction. The branches themselves are again made of segments, this time horizontal, of varying length (up to 5, maybe more?). Sometimes the first of those segments can even be vertical (2 blocks, maybe more?), giving the whole branch a more circular curve. And rarely, the side braches can be offset to the side by 2 blocks away from the source block rather than just 1, it still seems to be the same general structure, though.
Those form kind of a hollow sphere, or to be more precise, a box with the edges missing. The individual side planes can thereby be of varying width along each dimension, from 2 to 4, giving the whole structure a size of (4-6)³. There will be random blocks missing throughout and often the bottom part might be entirely missing, too, making it more dome-like. But it doesn't seem to happen that an entire side or the whole top is missing, beyond the individual block holes.
As to the seeding pattern of the structures, it's hard to say much from general observations. They seem to be generated at a frequency that roughly gives each individual coral structure a perimeter of just about its own size, with some areas clumping them a little more for the structures to penetrate each other more, and other areas where they have a little more "breathing room".