Skip to content

Instantly share code, notes, and snippets.

Created October 4, 2018 12:19
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
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 =={
// 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 = 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.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 ? : findSmallestNode(current);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment