...

/

Deletion in Binary Search Tree (Implementation)

Deletion in Binary Search Tree (Implementation)

Learn to write the implementation of the deletion function, which covers all the cases that were discussed previously.

Introduction

Implement the delete function for BSTs. You will build upon the code as you cater for each case.

1. Deleting an empty tree

Start with a skeleton function definition and cater for the first case. Return false if the root is null.

Press + to interact
Delete(Node currentNode,int value) {
if(root==NULL)
return false;
}

2. val not found

Search for the tree for the given data. If it’s not found, i.e., currentNode is null, return false.

Press + to interact
bool Delete(Node currentNode, int value)
{
if (root == null)
{
return false;
}
Node parent; //To Store parent of currentNode
// Search for the tree for the given data
while (currentNode != null && (currentNode.value != value))
{
parent = currentNode;
if (currentNode.value > value)
currentNode = currentNode.leftChild;
else
currentNode = currentNode.rightChild;
}
// Return true if currentNode is not null
if (currentNode != null)
return true;
return false;
}
Press + to interact
main.cs
BST.cs
using System;
namespace chapter_6
{
class Node
{
public int value;
public Node leftChild;
public Node rightChild;
public Node()
{
value = 0;
leftChild = null;
rightChild = null;
}
public Node(int val)
{
value = val;
leftChild = null;
rightChild = null;
}
}
class BinarySearchTree
{
Node root;
public BinarySearchTree(int rootValue)
{
root = new Node(rootValue);
}
public BinarySearchTree()
{
root = null;
}
public Node getRoot()
{
return root;
}
public Node 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;
}
public void insertBST(int value)
{
if (getRoot() == null)
{
root = new Node(value);
return;
}
insert(this.getRoot(), value);
}
public void inOrderPrint(Node currentNode)
{
if (currentNode != null)
{
inOrderPrint(currentNode.leftChild);
Console.WriteLine(currentNode.value);
inOrderPrint(currentNode.rightChild);
}
}
Node searchBST(int value)
{
//let's start with the root
Node currentNode = root;
while ((currentNode != null) && (currentNode.value != value))
{
//the loop will run until the currentNode IS NOT null
//and until we get to our value
if (value < currentNode.value)
{
//traverse to the left subtree
currentNode = currentNode.leftChild;
}
else
{ //traverse to the right subtree
currentNode = currentNode.rightChild;
}
}
//after the loop, we'll have either the searched value
//or null in case the value was not found
return currentNode;
}
public Node search(Node currentNode, int value)
{
if (currentNode == null)
return null;
else if (currentNode.value == value)
return currentNode;
else if (currentNode.value > value)
return search(currentNode.leftChild, value);
else
return search(currentNode.rightChild, value);
}
public bool Delete(Node currentNode, int value)
{
if (root == null)
{
return false;
}
// Search for the tree for the given data
while (currentNode != null && (currentNode.value != value))
{
if (currentNode.value > value)
currentNode = currentNode.leftChild;
else
currentNode = currentNode.rightChild;
}
// Return true if currentNode is not null
if (currentNode != null)
return true;
return false;
}
public bool deleteBST(int value)
{
return Delete(root, value);
}
}
}

3. Deleting a leaf node

First, search for the value given to delete while also saving the parent node. Once the node is found, check if ...