Borrar items de un TreeView

[delphi.com.ar]

Es un error MUY COMÚN, para eso existe un evento OnDeletion que se ejecuta cada ves que se elimina un nodo, a ahí puedes encargarte de eliminar lo que tengas en la propiedad Data.

Y agrego que para que esto sea mas rápido, evitando que re-dibuje el árbol cada ves que se elimina un nodo, te conviene hacer algo así:

TreeView1.Items.BeginUpdate;
try
  TreeView1.Items.Clear;
finally
  TreeView1.Items.EndUpdate;
end;

También lo puedes hacer a la hora de cargar los nodos. Estoy seguro que si tu árbol es tiene muchos nodos me lo vas a agradecer...

Saludos!

PD:
El hilo anterior fue para competir con Román en la respuesta mas corta!