Understanding binary-search-tree (BST) delete implementation with recursive calls

Question

I'm having some trouble understanding how to implement the delete operation in a BST. I can implement find() and insert() without much trouble and understand what's happening, but struggle with delete.

The deletion process as I understand involves updating the parent of the node we want to deletes right or left reference(depending), to reference either null, the child of the node we want to delete(when node to be deleted has one child), or replacing it with its in order successor(when node to be deleted has 2 children).

Most implementation I have seen like the Java one here. Seems to use recursion in a way that makes an explicit parent reference not necessary. I think this is where I keep getting confused.

Can anyone explain how the recursive calls here work and how they accomplish this?

Answer 1

in that link the recurrence is used to find the key while keeping a reference of the parent to the node as it returns the relevant node that will replace the node which is getting deleted. it also "deletes" the node its using to replace the original node using recurrence so that there aren't duplicates.

hope this is helpful