En rigor, según la letra, no es necesario usar un TAD. Lo que se pide es que si se usa un TAD sea uno de los que se vio en el curso (o sea, que no se innove con uno con operaciones a medida del problema) y que se especifique.
Sin embargo aunque no es necesario es difícil resolver el problema sin el concepto cola de árboles.
En tu implementación hay un problema menor que es que padre no está inicializado. La instrucción FS padre, hijo = t; solo inicializa hijo.
Pero hay un problema importante y es que no se visitan todos los nodos del nivel sino solo los hijos del primer nodo del nivel anterior.
Esto lo podés ver en que padre solo se modifique en el ciclo externo por lo que siempre es un nodo del camino que va desde la raíz hacia la hoja que (en un diagrama) está más a la izquierda.
En el siguiente ejemplo padre va a apuntar a los nodos A, B y D. Como nunca va a apuntar a C no va a visitar E y F
A
/ \
B C
/ \ /\
D E F
El árbol anterior con la representación ph-sh es el siguiente (los punteros sh se representan con -> y se excluyen todos los NULL)
En la solución cuando se visita C se deben encolar sus hijos E y F porque de otra forma ya no se puede acceder a ellos.
