I have an idea on how it could work, but I don't know how database intensive it would have to be. You can probably judge that when you read it.

Associate "users subscribed to this thread" information with the root node. Then when someone submits a node, you walk up its ancestor line to the root, get the list of subscribers, and send a message to all of them.

To make it manageable for users, you would probably also want to keep "threads I'm subscribed to" associated with the user. Keeping what is essentially the same data in two separate places is annoying, but otherwise you'd have to scan the entire node base to find which threads a particular user was subscribed to.

That was the idea that popped into my head when you said that nodes use a parent pointer representation. To be honest, I personally don't think I would use the feature very much because Recently Active Threads fulfills my needs in the thread-watching category.