insertar datos en dos tablas sin integridad referencial

[E*M*P*I*C*A*L]

Mi base de datos dispone de dos tablas, una tabla llamada arbol que contiene los campos 'id', 'ident' y 'categoria', la tabla mensaje costra de los campos 'id', 'autor', 'mensaje', 'fecha'. Para seleccionar los campos y construir el arbol de hijos no tengo problemas ya que uso una consulta con left join. El problema se me plantea cuando ingreso un mensaje nuevo en la tabla mensajes y tengo que insertar tambien los correspondientes datos en la tabla arbol.

¿Como se podria construir la consulta para que cuando ingrese los datos en la tabla mensajes inserte tambien los datos en la tabla arbol con el id de mensajes?

El campo id de la tabla mensajes es un int auto_increment, pero el id de la tabla arbol no.