Q: PN junction diode's free electrons When we look at the PN junction diode, there is always a depletion region, for which one side in negative and one side positive. The reason behind this is that the N side depletion region is positively charged because its free electrons have recombined with the p side.
My question is that if free electrons are not attached to any particular atom, then how come they leave a hole behind when they go to the P side ? aren't holes formed when the covalent bonds can accept an electron to make covalent bond with two electrons? Since these electrons were already free, they shouldn't leave a hole behind. 

A: I don't think your premise is correct.  When a p-type material (excess holes) joins an n-type material (excess electrons), some of these excess holes and electrons travel to the other side via diffusion and recombine with electrons and holes, respectively, on the opposite side.  These electrons and holes that diffuse to the other side are then gone via recombination, depleting them.  But, the p-type material has some electrons to begin with (it has excess holes), and the N-type material had some holes ( it has excess electrons), so  electons become  loose  on the P-side (when holes diffuse the N -side) and holes become loose on the N-side (when electrons diffuse to the p-side) and they line up at the junction boundary where the charged carriers were depleted.  This process achieves equilibrium when no more carriers travel across the junction.
When the junction is reverse biased, the holes in the p-type material are attracted to "negative polarity" of the voltage acrosss the junction ,  leaving more electrons behind at the junction.  Similarly, the positive polarity on the n-side attracts the electrons on that side, leaving the holes behind at the junction.  This increases  the opposing electric field at the junction which further opposes the exchange of carriers between the p and n materials thus expanding this depletion region further.   The holes and electrons are already there in the materials in different densities (p-type is mostly holes, but has electrons too, n-type is mostly  electrons, but also has holes.  

A: Holes certainly have positive charge, but you are wrong attributing any positive charge to holes. A hole, as understood in semiconductor physics, is a vacancy in the valence band. The n side of the depletion zone has no holes, still it has a positive space charge because it's a n-type semiconductor. Remind that a neutral n-type semiconductor has some density of electrons in the conduction band. What happens when they depart?
If you, instead, deem a "hole" any vacancy below the Fermi level, then it's something different from charge carriers.

A: Even though Electrons are majority charge carriers in n -type material, it is still electrically neutral   since ideally the number of positively charged protons in the nuclei is still equal to the number of free and orbiting negatively charged electrons in the structure. Same goes for p-type. 
Before the  pn junction is  formed, there are as  many electrons  as  protons  in the  n-type material, making the material neutral in terms  of net  charge. The  same is  true for the  p-type material. When the  pn junction is  formed, the  n region loses  free electrons  as  they diffuse across the junction, making it more positive than p-type. This is what makes the n-type positive and p-type negative. 
Hope that answers your question. 
Reference: Floyd - Electronic Devices

A: 
My question is that if free electrons are not attached to any particular atom, then how come they leave a hole behind when they go to the P side ? 

They do not.
A pure (undoped) semiconductor has an equal amount of mobile charge carriers (electrons and holes). A very useful property of semiconductors is that you can control the electron and hole concentrations by "doping" the semiconductor. You do this by introducing a small amount of atoms that either add (donor dopants) or remove (acceptor dopants) an electron from the semiconductor. When you do this, the number of mobile charge carriers of each type change according to the law of mass action:
$$
np=n_i^2
$$
Where \$n\$ and \$p\$ are the electron and hole concentrations and \$n_i\$ is the intrinsic carrier concentration, which is the number of electrons and holes in the undoped semiconductor. By adding donor atoms to the semiconductor you can increase the electron concentration by an amount equal to the donor concentration. Doing so also reduces the hole concentration in that area. However, the total charge of the semiconductor stays zero. The total net charge from the mobile charge carriers is cancelled out by fixed charge: ionized dopants. 
To address the question directly:

how come they leave a hole behind when they go to the P side ?

They do not, they leave behind a positively charged ionized donor. 

aren't holes formed when the covalent bonds can accept an electron to make covalent bond with two electrons?

No. Holes are created when an acceptor ionizes and creates a hole. Holes exist due to a bunch of quantum mechanics that I can't write down off the top of my head. But its best to think of holes as just like electrons but with a positive charge. People might try to tell you to think of a hole as just the absence of an electron, but don't fall for it. Holes are very much not just the absence of an electron and it will confuse you to think of them as such. 

Since these electrons were already free, they shouldn't leave a hole behind. 

The electrons were free, which is precisely why they leave behind an ionized donor. The ionized donor is the reason the free electron was there in the first place.
