Python Data Structures and Algorithms

Deleting nodes

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
• One child
• Two children

The first scenario is the easiest to handle. If the node about to be removed has no children, we simply detach it from its parent:

Because node A has no children, we will simply dissociate it from its parent, node Z.

On the other hand, when the node we want to remove has one child, the parent of that node is made to point to the child of that particular node:

In order to remove node 6, ...