Removing Data
Removing data in BST is a quite complex algorithm compare to other methods.
There are 3 scenarios for removing data in BST:
- Find the node to be deleted.
- If the node doesn't exist, exit.
- Leaf (terminal) node.
- Delete and remove parent's pointer to deleted node.
- Non-leaf node.
- Find the child to replace the deleted node.
We will focus on the third scenario, if the deletion occured on non-leaf node.
Basically, it has 3 scenarios within.
Removed node has no right child -> Remove(8)
Left child replaces the removed.
Find node to removed.
Has no right child.
Promote left child.
Removed right child nas no left. -> Remove(6)
Right child replaces the removed.
Find node to remove.
Node right has no left.
Promote right child.
Removed right child has left child -> Remove(6)
Right child's left-most child replaces removed.
Find node to remove.
Node right has left.
Find right's left-most child.
Promote left-most child.