Skip to content

Instantly share code, notes, and snippets.

@maxskorr
Created October 27, 2015 10:54
Show Gist options
  • Save maxskorr/5b53ace5c785a64b447f to your computer and use it in GitHub Desktop.
Save maxskorr/5b53ace5c785a64b447f to your computer and use it in GitHub Desktop.
private boolean delete(Node<T> node, T value) {
if (node == null) {
return false;
}
if (value.compareTo(node.value) > 0) {
return delete(node.right, value);
}
if (value.compareTo(node.value) < 0) {
return delete(node.left, value);
}
if (value.equals(node.value)) {
Node<T> parent = findParentNode(root, value);
if (parent == null) {
return false;
}
// node has no children
if (node.right == null && node.left == null) {
if (parent.left != null && parent.left.equals(node)) {
parent.setLeft(null);
size--;
return true;
}
if (parent.right != null && parent.right.equals(node)) {
parent.setRight(null);
size--;
return true;
}
}
// Node has one child
if (node.left == null) {
if (parent.left != null && parent.left.equals(node)) {
parent.setLeft(node.right);
size--;
return true;
}
if (parent.right != null && parent.right.equals(node)) {
parent.setRight(node.right);
size--;
return true;
}
}
if (node.right == null) {
if (parent.left != null && parent.left.equals(node)) {
parent.setLeft(node.left);
size--;
return true;
}
if (parent.right != null && parent.right.equals(node)) {
parent.setRight(node.left);
size--;
return true;
}
}
// node has two children
Node<T> minNode = findMin(node.left);
if (minNode == null) {
return false;
}
Node<T> minNodeParent = findParentNode(root, minNode.value);
minNodeParent.setLeft(null);
node.setValue(minNode.value);
return true;
}
return false;
}
public boolean delete(T value) {
return delete(root, value);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment