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

Change-Id: I7e1b021b0c7d2b4032e559f13247e81dd4ca9181
Closes-Bug: #1336654