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 datawhile (currentNode != null && (currentNode.value != value)){parent = currentNode;if (currentNode.value > value)currentNode = currentNode.leftChild;elsecurrentNode = currentNode.rightChild;}// Return true if currentNode is not nullif (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 rootNode currentNode = root;while ((currentNode != null) && (currentNode.value != value)){//the loop will run until the currentNode IS NOT null//and until we get to our valueif (value < currentNode.value){//traverse to the left subtreecurrentNode = currentNode.leftChild;}else{ //traverse to the right subtreecurrentNode = currentNode.rightChild;}}//after the loop, we'll have either the searched value//or null in case the value was not foundreturn 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);elsereturn search(currentNode.rightChild, value);}public bool Delete(Node currentNode, int value){if (root == null){return false;}// Search for the tree for the given datawhile (currentNode != null && (currentNode.value != value)){if (currentNode.value > value)currentNode = currentNode.leftChild;elsecurrentNode = currentNode.rightChild;}// Return true if currentNode is not nullif (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 ...