Sounds like you need to cross link the left and right children to each
other after deleting (or maybe before),
rather than to the node  you are deleting (which is what they are linked
to before the delete).