Hice algunas pruebas y vi que (al menos en éste caso) no es necesario eliminar la referencia hacia el padre, parece que C# administra muy bien los recursos.
Hice la prueba de la siguiente forma:
Al objeto nodo le agregué dos atributos para poder identificarlo: Nivel e Index y agregué un destructor para verificar que el nodo sea eliminado
~Nodo()
{
System.Diagnostics.Trace.WriteLine("Matando hijo "+Index+" del nivel " + Nivel);
}
Después genero un árbol, donde el nodo root tiene tres hijos y al segundo hijo le agrego otro nodo hijo y a éste le agrego 10 más
Nodo root = new Nodo();
root.Add();
root.Add();
root.Add();
root[1].Add();
root[1][0].Add();
for(int i=0; i<10;i++)
root[1][0].Add();
Después al borrar el segundo nodo, quien tiene mayor profundidad veo que sale en el log cada nodo eliminado al forzar el llamado del GC:
root.Del(1);
GC.Collect();
Consola:
Matando hijo 4 del nivel 3
Matando hijo 3 del nivel 3
Matando hijo 2 del nivel 3
Matando hijo 1 del nivel 3
Matando hijo 0 del nivel 3
Matando hijo 8 del nivel 3
Matando hijo 1 del nivel 1
Matando hijo 0 del nivel 2
Matando hijo 7 del nivel 3
Matando hijo 10 del nivel 3
Matando hijo 9 del nivel 3
Matando hijo 6 del nivel 3
Matando hijo 5 del nivel 3
Para descartar errores guarde el nodo eliminado en otra variable temporal y efectivamente al invocar al GC no apareció nada en la consola
temp = root[1];
root.Del(1);
GC.Collect();
Después puse en null la variable temp, llame al GC y volvió a aparecer en consola cada nodo eliminado
temp = null;
GC.Collect();
Consola:
Matando hijo 4 del nivel 3
Matando hijo 3 del nivel 3
Matando hijo 2 del nivel 3
Matando hijo 1 del nivel 3
Matando hijo 0 del nivel 3
Matando hijo 8 del nivel 3
Matando hijo 1 del nivel 1
Matando hijo 0 del nivel 2
Matando hijo 7 del nivel 3
Matando hijo 10 del nivel 3
Matando hijo 9 del nivel 3
Matando hijo 6 del nivel 3
Matando hijo 5 del nivel 3
El porque
Pues resulta que aunque los nodos hijos tengan una referencia al nodo padre, ésta referencia es una referencia débil (WeakReference) ya que el nodo hijo esta en el Heap.
En la primer prueba, cuando se elimina el nodo1 ya no hay nadie en el stack que haga referencia éste, entonces el GC lo elimina junto con todos sus descendientes, aunque existen referencias entre el nodo1 y sus hijos, éstas referencias están dentro del Heap, por lo tanto, son candidatos a eliminarse.
En la prueba 2 se está pasando la referencia del nodo1 a la variable temp la cual si está en el stack, por lo tanto, el nodo1 y sus hijos no serán eliminados hasta que temp se iguale a null.
Aqui hay una mejor explicación de las referencias débil