removeNode detaches the node from the scene graph and drops the reference, so that (assuming you're not keeping any other references) it may be garbage collected.
Deleting a scene works like deleting any object in Python - you don't, you just drop all the references to it, so that it is garbage collected.
Parents hold references to child nodes, though, so that's why there's removeNode() which also detaches the given node from the scene graph.
There is also removeAllChildren, but it doesn't do any magical deleting either - it simply invokes removeNode on all children of the node, but this won't have a particular benefit over removeNode if you cleared up your references correctly. In that sense, removeAllChildren doesn't solve your problem, since the child nodes won't be removed either until their references are cleared as well.
One thing to mention is that if you have used setPythonTag referring to another node on any of the nodes, you have created a circular reference which must be explicitly broken first before you drop your last reference.