If the backup server has access to the tree structure, then the backup isn't fully encrypted, or at least the metadata isn't. Now you need to have a conversation about what metadata is allowed to be stored unencrypted on the server and what metadata isn't. If you want a fully encrypted deduplicated backup system, I don't see how it's possible to prune without the ability to decrypt, because there's no way to know what needs to be pruned.