Apparently you can only free() dynamically allocated ones on the heap

AIUI, when you create using Newx(), you are allocating dynamically - and you'll leak memory if you don't Safefree() those dynamically allocated variables when they go out of scope.

Incidentally, DESTROY() doesn't have to be a perl sub.
You could dispense with that perl sub and place it in the C code as something like (untested):

void DESTROY(Node* self) {
    warn("destroying self");
    Safefree(self);
}
[download]

However, you may well find that there are additional things to Safefree (again untested):

void DESTROY(Node* self) {
    warn("destroying self");
    Safefree(self-> parent);
    Safefree(self-> sv);
    Safefree(self);
}
[download]

Admittedly, you've then lost the identification of the actual object that's being Safefree'd - though I think that could be easily addressed.
And I'm not sure how the self-referential nature of the Node object impacts upon things.

Cheers,
Rob