Fix bug with nodes deletion and add test to prevent this in future.

Change-Id: I7e1b021b0c7d2b4032e559f13247e81dd4ca9181
Closes-Bug: #1336654
(cherry picked from commit 4b5a0003f6c372229500f31b4a4e4d6708b154fb)