Deletion in a Binary Search Tree

In this lesson, we are going to learn how nodes are deleted in binary search trees. We will take a look at a few node deletion scenarios and what to do in each one.

We'll cover the following

Introduction

We 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 and, once found, you’ll make it None by making the left or right child of its parent None. However, to make things simpler, we’ve identified six possible cases involved in BST node deletion. We’ll 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

Let’s 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, we simply remove that leaf node. We do this by making the parent node’s left or right child (whichever one the leaf node was) None. Have a look at the following example for a demonstration

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.