<p>Today, videos have established themselves as one of the most influential forms of media, not only in the entertainment field but also in education. Creating explanatory and educational videos, especially those aimed at explaining algorithms, presents a considerable challenge because trustworthiness is essential in this area. Additionally, this process demands significant effort, both in conceptualizing the execution of the algorithm and in translating the explanations into visually effective and understandable slides. To address this problem, we propose a transparent architecture for the automatic generation of explanatory videos based on the execution traces of algorithms, particularly those that utilize state-space search. This combines syntactic analysis and natural language generation modules able to transform execution traces into parse trees. From these parse trees, a set of frames that includes visual graphics and detailed textual explanations is generated. Finally, the frames are organized in sequence to produce a video narrated by a virtual teacher, providing a dynamic and accessible educational experience. The result is an expert system capable of automatically generating explanatory videos that have been evaluated by two key groups: teachers and students in the area. The evaluation was conducted using a questionnaire based on the Learning Object Review Instrument standard, which considered various aspects, such as the quality of the video and its content, the motivational capacity, and the presentation design of the material.</p>