Data Structures for Coding Interviews in C++/

...

/

Deletion in Binary Search Tree (Implementation)

Deletion in Binary Search Tree (Implementation)

We will now write the implementation of the deletion function, which covers all the cases that we discussed previously.

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

...