What's the most intuitive way to think about BST deletion?
Zero and one child make sense to me. The two-children case is where I get lost. Why is replacing with the successor (or predecessor) always safe? And how do you all keep straight which one to use?
Comments
Either successor or predecessor works. Just be consistent with whichever your implementation uses.
The successor is the smallest value in the right subtree, so it's bigger than everything on the left and smaller than everything else on the right. That's why it can take the deleted node's spot.