Another important operation on a BST is the deletion or removal of nodes. There are three scenarios that we need to cater for during this process. The node that we want to remove might have the following:
- No children: If there is no leaf node, directly remove the node
- One child: In this case, we swap the value of that node with its child, and then delete the node
- Two children: In this case, we first find the in-order successor or predecessor, swap the value with it, and then delete that node
The first scenario is the easiest to handle. If the node about to be removed has no children, we simply remove it from its parent:
