Er zijn hier twee(OK eigenlijk 4, to do en call incl.!) werkwoorden: try en leave , -try-, in de hoofdzin en -leave- in de bijzin. Het geheel is in de verleden tijd. De hoofdzin heeft daarom -did try- (did toegevoegd omdat het een vraag betreft en daarom blijft -try- onveranderd) en de bijzin heeft -left-. De man is de deur uit, oftewel he is gone,has disappeared. -Did- heeft geen invloed oftewel niets te maken met de bijzin. Een beter argument voor corrigeren door je docente zou zijn geweest: Did you try to call the man, who HAD (already) left (earlier).
Verder ben ik altijd happier als in plaats van the man, THAT , the man, who wordt gebruikt. That gebruik ik voor dingen niet voor personen, maar het wordt allebei tegenwoordig geaccepteerd….
Ik hoop, dat je je docente hebt tegen gesproken, in ieder geval je zin verdedigd hebt.