Density functional calculations of structural and electronic properties of stoichiometric and nonstoichiometric CdTe clusters, containing up to few tens of atoms, are carried out using projector augmented wave method. Molecular dynamics has been performed for Cd₁₂Te₁₂ and Cd₁₅Te₁₅ to predict the structure corresponding to global energy minimum. Cage type structures and bulk fragments, both in zinc blende and wurtzite structures, are used as starting geometries and conjugate gradient method is used to locate the local energy minima for other clusters. The aim of these calculations is to get the energetically favorable probable structures, to be compared with the experimentally known structures. Clusters are relaxed both in vacuum and in the presence of surface passivating ligands and the resulting structural rearrangement is analyzed. As expected, passivation increases the stability of an individual cluster, as indicated by specific properties like binding energy, vertical detachment energy, electron affinity etc. Passivation also locks the symmetry for three-dimensional structures but the small Cd_nTe_n (1 ≤ n ≤ 6) clusters, which are planar, attain higher symmetry structures on passivation. We observe `self-healing' mechanism viz., opening of optical gap on relaxation without the aid of passivating ligand, in CdTe clusters as observed in CdSe clusters [A. Puzder et al., Phys. Rev. Lett. 92, 217401 (2004)]. However, we note that 'self-healing' is a stoichiometry dependent phenomenon. Te atoms are found to achieve a total coordination of 4 on passivation, a fact useful in chemical synthesis of nanoclusters.