Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C++

Deletion in Binary Search Tree (Implementation)

Explore how to implement deletion operations in binary search trees using C++. Understand and handle each scenario from deleting empty trees, leaf nodes, nodes with one or two children, and apply these concepts with an efficient code example.

We'll cover the following...

Introduction #

Let’s implement the delete function for BSTs. We’ll build upon the code as we cater for each case.

1. Deleting an empty tree #

Let’s start with a skeleton function definition and cater for the first case. We return false if the root is NULL.

C++
Delete(Node* currentNode,int value) {
    if(root==NULL)
        return false;
}

2. val not found #

We search for the tree for the data given, and if it’s not found, i.e., currentNode is NULL, we return false.

C++
bool Delete(Node* currentNode,int value) {
        if(root==NULL){
            return false;
        }
        Node* parent; //To Store parent of currentNode
        while(currentNode!=NULL && (currentNode->value != value)) {
            parent=currentNode;
            if (currentNode->value > value)
                currentNode=currentNode->leftChild;
            else
                currentNode=currentNode->rightChild;
        }
        if(currentNode==NULL)
            return false;
}
C++
#include "BST.h"
Node::Node() {
  value = 0;
  leftChild = NULL;
  rightChild = NULL;
}
Node::Node(int val) {
  value = val;
  leftChild = NULL;
  rightChild = NULL;
}
BinarySearchTree::BinarySearchTree() {
  root = NULL;
}
BinarySearchTree::BinarySearchTree(int rootValue) {
  root = new Node(rootValue);
}
Node * BinarySearchTree::getRoot() {
  return root;
}
Node * BinarySearchTree::insert(Node * currentNode, int val) {
  if (currentNode == NULL) {
    return new Node(val);
  }
  else if (currentNode -> value > val) {
    currentNode -> leftChild = insert(currentNode -> leftChild, val);
  } 
  else {
    currentNode -> rightChild = insert(currentNode -> rightChild, val);
  }
  return currentNode;
}
void BinarySearchTree::insertBST(int value) {
  if (getRoot() == NULL) {
    root = new Node(value);
    return;
  }
  insert(this -> getRoot(), value);
}
bool BinarySearchTree::Delete(Node * currentNode, int value) {
  if (root == NULL) {
    return false;
  }
  Node * parent; //To Store parent of currentNode
  while (currentNode != NULL && (currentNode -> value != value)) {
    parent = currentNode;
    if (currentNode -> value > value)
      currentNode = currentNode -> leftChild;
    else
      currentNode = currentNode -> rightChild;
  }
  if (currentNode == NULL){
    return false;
  }
  return false;
}
bool BinarySearchTree::deleteBST(int value) {
  return Delete(root, value);
}
void BinarySearchTree::inOrderPrint(Node * currentNode) {
  if (currentNode != NULL) {
    inOrderPrint(currentNode -> leftChild);
    cout << currentNode -> value << endl;
    inOrderPrint(currentNode -> rightChild);
  }
}

3. Deleting a Leaf Node

...