Skip to content

Instantly share code, notes, and snippets.

@xnorcode
Created October 4, 2018 12:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save xnorcode/94fb307dc3d57ec9db19168bd6a33e59 to your computer and use it in GitHub Desktop.
Save xnorcode/94fb307dc3d57ec9db19168bd6a33e59 to your computer and use it in GitHub Desktop.
Find and delete a given node in a BST and then reorganise it
...
// Delete a node in the BST
static void delete(int val){
delete(root, val);
}
// Delete a node in the BST recursive helper method
private static Node delete(Node current, int val){
// could not find node in BST
if(current == null) return null;
// Found node, lets delete it
if(val == current.data){
// if node has no children simply delete it
if(current.left == null && current.right == null) return null;
// if node has only one child, remove that node and connect
// its child directly to parent
if(current.left == null) return current.right;
if(current.right == null) return current.left;
// if node has two children we need to reorganise them
// find the smallest node on the right subtree
int smallestValue = findSmallestNode(current.right);
// replace it with the current node
current.data = smallestValue;
// then delete it from the right subtree
current.right = delete(current.right, smallestValue);
// end method
return current;
}
// check on the left side of the BST
if(val < current.data){
current.left = delete(current.left, val);
return current;
}
// check on the right side of the BST
current.right = delete(current.right, val);
return current;
}
// helper method to find smallest node on a Tree
private static int findSmallestNode(Node current){
return current.left == null ? current.data : findSmallestNode(current);
}
...
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment