Hello everybody. Here is my remove method for bst. As you all know, there are 3 cases to consider while removing a node from bst. For the last case, when a node (which is to be removed) has 2 children, I want to use predecessor instead of successor to change removed node with new one. So for this, I'm searching largest element on the left subtree. But my code still takes successor instead of predecessor and I do not understand why. Any ideas?
public void delete(T data) {
root = delete(root, data);
}
private Node<T> delete(Node<T> here, T data) {
if (here != null) {
if (data.compareTo(here.getData()) < 0) {
here.left = delete(here.left, data);
} else if (data.compareTo(here.getData()) > 0) {
here.right = delete(here.right, data);
} else {
here = deleteNode(here);
}
}
return here;
}
private Node<T> deleteNode(Node<T> here) {
// cases 0 and 1
if (here.left == null)
here = here.right;
else if (here.right == null)
here = here.left;
// case 2
else {
// go left
// destroy the largest node on the left
// find the victim
Node<T> big = here.left;
Node<T> last = null;
while (big.right != null) {
last = big;
big = big.right;
}
here.data = big.data;
if (last == null) {
here.left = big.left;
} else {
last.right = big.left;
}
}
return here;
}