Deletion in Binary Search Trees

In this lesson, we are going to learn how deletion operations are performed in Binary Search Trees.

We'll cover the following

Introduction

In this lesson, we are going to look at the three deletion cases and the steps required to perform deletion in each case.

The three cases are given below:

  • Deletion at Leaf Node
  • Deletion at Parent Node
    • Node has only one child
    • Node has two children

Now let’s look at all the case one by one.

Deletion at Leaf Node

If the node we want to delete is present at the leaf node in a Binary Search Tree, we simply remove that leaf node. After deletion, its parent node will point to null. If the leaf node was the left child of Node X, then make leftChild of Node X null; if it was the right one, then make the rightChild pointer of node X point to null. See the following example for clarification:

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