Created
October 4, 2018 12:19
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
... | |
// 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