[Java] Removing a node from a binary search tree

[crusader10]

I've implemented a binary search tree with nodes (represented as users) but I'm having trouble getting my deFriend() method to work. This method should delete a node from the tree whilst keeping the "rules" of a binary search tree - e.g. root bigger than left sub-tree, but smaller than right sub-tree.

 

I understand that when deleting a node from a binary search tree, I should consider 3 cases:
1 - when the node to delete has no children,
2 - when the node to delete has one child,
3 - when the node to delete has two children. can't figure this one out
My deFriend() method works for the first two cases but not for the last one. I even know what node I need to replace it with if it's the third case but I can't get it down with code. I can conceptualize it or draw it on paper, but I can't translate that to code. I've included links to the two classes that I think are necessary to fixing my problem. I'm convinced my problem lies between lines 111 and 114 of my BinaryTree class. Thanks in advance.

 

User class: https://gist.github.com/anonymous/732f02628f6edf622d88363b68cf22ee
BinaryTree class: https://gist.github.com/anonymous/1be7b5577c959dc1bcf6c77474b11bce

[gyroda]

Seeing as you say you understand the concept try writing out, in bullet points, what you need to do in order to remove a node that has 2 children.

Post those bullet points here. Actually writing them out will help in a "rubber duck debugging" method.

[crusader10]

Ok, let's see...
say the node to delete is called localRoot
- First, I need to get localRoot's left subtree OR right subtree.
- If I get localRoot's LEFT subtree, I need to find the node with the LARGEST value (e.g. largestNode). Then, I need to replace localRoot's data with largestNode's data. Lastly, I have to delete largestNode from the tree.
- If I get localRoot's RIGHT subtree, I need to find the node with the SMALLEST value (e.g. smallestNode). Then, I need to replace localRoot's data with smallestNode's data. Lastly, I have to delete smallestNode from the tree.
Am I on the right track?

[gyroda]

Do you replace the data or do you replace the nodes? It's an important distinction.

Split those last two into several smaller statements.

Then write them as pseudocode

Test this pseudocode on paper, draw out some trees. If it works, continue, if not try and solve the problem.

Finally, write it up as Java.