Removal from Binary Trees
It's not hard. Find the node, like you might expect. Then, there are three cases:
The node has no children. Just delete the node.
The node has one child. Move its child up to take its place.
The node has two children. Pick one of the children at random, and replace this node's data with the data from that child. Then call remove on that child.
Removal from Binary Search Trees
The cases for zero or one child are the same as above.
The node has two children. Find either the largest element of its left subtree, or the smallest element of its right subtree; call this data d. Replace this node's data with d. Now call remove on that subtree, with argument d.
If we're not interested in balancing the tree, we can be consistant: always find the smallest element of the right subtree, for example. If we DO care, we can institute some randomness here, and on average, we'll keep a relatively balanced tree, though we have no guarantees.
To implement this, first make methods findMax and findMin that take a Node as an argument, that returns the largest element of the tree rooted at that Node.