BINARY SEARCH TREES: DELETION

I’m continuing my learning of the Binary Search Trees, so this post contains notes that I took on DELETION in the Binary Search Tree.

Looking at some cases in deleting a node from the Binary Search Tree.

Case 1: Deleting a node with no children.

Case 2: Deleting a node with 1 child.

Case 3: Deleting a node with 2 children.

_______500_______

/ \

__250__ __750_

/ \ / \

150 350 650 850

/ \ / \ / \ / \

100 180 270 400 600 700 830 980

case 1: if you want to delete a node with no children, which is 700, from the binary tree, which is a leaf node, you would remove the reference form the parent node and set it to null.

_______500_______

/ \

__250__ __750_

/ \ / \

150 350 650 850

/ \ / \ / \ / \

100 180 270 400 600 null 830 980

case 2: if you want to delete a node with 1 child, which is 650, from the binary tree because of the previous example, you would reference the 650 node, which is a parent, and then reference the only child of 650.

_______500_______

/ \

__250__ __750_

/ \ / \

150 350 650 850

/ \ / \ / \ / \

100 180 270 400 null null 830 980

use the following tree as an example for case 2:

_______500_______

/ \

__250__ __750_

/ \ / \

null 350 650 850

/ \ / \ / \

270 400 600 700 830 980

case 2: if you want to delete a node with 1 child, which is 250, you would reference the 250 node, which is a parent, and then reference the only child of 250.

use the following tree as an example for case 3:

_______500_______

/ \

__250__ __750_

/ \ / \

150 350 650 850

/ \ / \ / \ / \

100 180 270 400 600 700 830 980

case 3: if you want to delete a node with 2 children, which is 700, from the binary tree, there are two ways:

1. search for a replacement for 750 within the left sub-tree of 750.

You want to pick a value which satisfies the binary search tree property, that the left child’s value must always be less than its parent’s value and the right child’s value must be greater than its parent’s value.

So, we want to find the largest value within the left subtree of 750 to replace the 750 node with.

In this case, the largest value within the left subtree of 750 is the value of the 700 node.

This also means that the value of the 700 node within the 650 subtree must be removed, because there cannot be a duplicate value in a binary tree.

The duplicate value of the 700 node, in the subtree of 650, is set to null.

this is what the tree would look like using the first way to delete a node with 2 children:

_______500_______

/ \

__250__ __750_

/ \ / \

150 350 650 850

/ \ / \ / \ / \

100 180 270 400 600 null 830 980

use the following tree as an example for case 3 part 2:

_______500_______

/ \

__250__ __750_

/ \ / \

150 350 650 850

/ \ / \ / \ / \

100 180 270 400 600 700 830 980

2. search for a replacement for 750 within the right sub-tree of 750.

So, we want to find the smallest value within the left subtree of 750 to replace the 750 node with.

In this case, the smallest value within the left subtree of 750 is the value of the 830 node.

This also means that the value of the 830 node within the 650 subtree must be removed, because there cannot be a duplicate value in a binary tree.

The duplicate value of the 830 node, in the subtree fo 850, is set to null.

BINARY SEARCH TREES: DELETION

There will be two deletion methods

1. in the BTS class — making the initial call.

2. in the node class.

class BTS {

delete(data) {

if(this.root)

// if there is a root node, then we can search for the node to delete

this.root = this.root.delete(data);

// if there is a root node, then we pass in the data and start looking for the data in the binary search tree we want to delete.

}

}

class Node {

delete(data){

if(data < this.data & this.left)

// If the data we want to delete from the binary search tree is less than the data node we’re currently at and if the current data has a left child node, then do the following.

// If the data we want to delete from the binary search tree is greater than the data node we’re currently at and if the current data has a left child node, then skip down the first ‘else if’ statement.

this.left = this.left.delete(data);

// If the data we want to delete from the binary search tree is less than the data node we’re currently at and if the current data has a left child node, then we can start the search to find the data we want to delete in the left subtree.

else if (data > this.data && this.right)

// If the data we want to delete from the binary search tree is greater than the data node we’re currently at and if the current data has a right child node, then do the following.

this.right = this.right.delete(data);

// If the data we want to delete from the binary search tree is greater than the data node we’re currently at and if the current data has a right child node, then we can start the search to find the data we want to delete in the right subtree.

else {

// If both the if statements fail “if(data < this.data & this.left)” and “else if (data > this.data && this.right)”, then do the following

// If the data you want to delete is equal to this.data, that means we have found the node we want to delete, then do the following.

if(this.data == data){

// If the data you want to delete is equal to this.data, that means we have found the node we want to delete, then do the following.

if(this.right & this.left){

// Case 3: Deleting a node with 2 children.

let minVal = this.right.findMin();

// in the right subtree, find the lowest value and set it as minVal.

this.data = minVal;

// after finding the lowest value in the right subtree, set that lowest value as this.data

this.right = this.right.delete(minVal);

// after finding the lowest value in the right subtree, delete that duplicate lowest value in that right subtree.

}

else if(this.left)

// Case 2: Deleting a node with 1 child.

// if a subtree only has a left child, then return the left child

return this.left;

// Case 2: Deleting a node with 1 child.

// if a subtree only has a left child, then return the left child

else if(this.right)

// Case 2: Deleting a node with 1 child.

// if a subtree only has a right child, then return the right child

return this.right;

// Case 2: Deleting a node with 1 child.

// if a subtree only has a right child, then return the right child

else

// Case 1: Deleting a node with no children.

// if a node does not have a child or children, then it is called a leaf node.

// Leaf: A node that does not have any children nodes.

return null;

// Case 1: Deleting a node with no children.

}

}

return this;

// after all the steps have been completed, return the node we’re currently at.

}

}

BINARY SEARCH TREES: DELETION

The purpose of this method is to find the smallest value within the correct subtree and return that value.

findMin() can be implemented either Recursively or Iteratively.

RECURSIVE

findMin(){

// findMin() has no parameters.

// We need to keep going left till we can’t go left anymore.

if(this.left)

// if there is a left child then implement the findMin() method on the left subtree.

// if there is not a left child (which means the smallest value is found) then skip down to the else statement below and return this.data.

return this.left.findMin();

// if there is a left child then implement the findMin() method on the left subtree.

else

// if there is not a left child (which means the smallest value is found) then return this.data.

return this.data

// if there is not a left child (which means the smallest value is found) then return this.data.

}

ITERATIVE

findMin(){

// findMin() has no parameters.

// We need to keep going left till we can’t go left anymore.

let current = this;

// we need to save the reference of the current node we’re at

while(current.left)

// this will traverse the tree

current = current.left

// this will keep going left till you can’t go left anymore.

return current.data;

// this will return the smallest value.

}

Deleting a node in a Binary Search Tree can be very fast.

I will continue my learning of the Binary Search Tree.