Sachverhalt: A. Am 7. August 2007, um 13.05 Uhr, geschah auf einer Baustelle der Bauunternehmung C._ AG in Kilchberg ein tödlicher Unfall. Der Bauführer A._ hatte angeordnet, dass der Bauarbeiter D._ und der Hilfsarbeiter E._ gemeinsam den Rückbau einer Baugrubenspriessung vornehmen. Am Unfalltag wollte D._ die Stahlträger von einem Kran wegheben lassen, nachdem er sie zuvor angeschnitten hatte. Während er sich entfernte, um den Kran zu besorgen, blieb E._ zurück. In der Folge begab sich dieser aus ungeklärten Gründen in die Baugrube, die sich unter den Stahlträgern befand. Dort wurde er von einem herabstürzenden Träger erschlagen. B. Die Staatsanwaltschaft Limmattal/Albis eröffnete eine Strafuntersuchung wegen fahrlässiger Tötung gegen A._, D._ und B._, den Geschäftsführer der C._ AG. Mit Verfügung vom 5. Dezember 2008 wurde die Untersuchung eingestellt. Die Eltern des Verstorbenen, X._ und Y._, erhoben dagegen einen Rekurs, den das Obergericht des Kantons Zürich am 16. Juni 2009 abwies. Gegen diesen Entscheid führten die Eltern Beschwerde in Strafsachen. Das Bundesgericht hiess diese gut, hob den angefochtenen Entscheid auf und wies die Sache zu neuer Entscheidung an das Obergericht zurück (Urteil 6B_601/2009 vom 24. November 2009). C. Am 18. August 2010 stellte die Staatsanwaltschaft Limmattal/Albis die Strafuntersuchung gegen D._ erneut ein, während sie gegen A._ und B._ Anklage erhob wegen fahrlässiger Tötung im Sinne von Art. 117 StGB. Der Einzelrichter in Strafsachen des Bezirksgerichts Horgen sprach A._ am 1. Dezember 2010 frei. Die dagegen erhobene Berufung der Eltern wies das Obergericht des Kantons Zürich am 15. März 2012 ab. D. X._ und Y._ führen gegen das obergerichtliche Urteil Beschwerde in Strafsachen und beantragen, A._ sei anklagegemäss schuldig zu sprechen, angemessen zu bestrafen und zu verpflichten, Genugtuung und Schadenersatz zu bezahlen. Sie ersuchen um unentgeltliche Rechtspflege und Verbeiständung. E. A._ stellt Antrag auf Abweisung der Beschwerde. Die Vorinstanz und die Oberstaatsanwaltschaft verzichteten auf eine Vernehmlassung. 