Deletion in Binary Search Tree

Introduction

In this lesson, you are going to study how a node is deleted in a BST. In general, to delete a node in a BST, you will search for it. Once it is found, you’ll free the space taken by that node, and you will re-allocate its left and right-subtree (if present). To make things simpler, we’ve identified four possible cases involved in BST node deletion. You will tackle each one separately:

1. Deleting in an empty tree
2. Deleting a node with no children, i.e., a leaf node
3. Deleting a node which has one child only
   1. Deleting a node which has a right child only
   2. Deleting a node which has a left child only
4. Deleting a node with two children

Look at each of these in detail:

1. Deleting an empty tree

If the given starting node is null, then do nothing and return False. This is an edge case for error handling.

2. Deleting a leaf node

When the node to be deleted is a leaf node in a binary search tree, you will simply free the space taken by that leaf node. Then make the parent node’s left or right child (whichever one the leaf node was) null. Have a look at the following example for a demonstration.