Challenge: Delete a Node with Two Children in a Binary Search Tree
Hint 1: This challenge works best when combining what you’ve learned in the lesson on finding the min and max values in a binary tree with the code from the previous lessons on removing elements from a binary tree.
Hint 2: Once you find the minimum value for the right side tree, you recursively remove the node with that value from the tree, then replace the value of the target node with the minimum value you found.
Solution
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
this.remove = function(value) {
if (this.root === null) {
return null;
}
var target;
var parent = null;
// Find the target value and its parent
(function findValue(node = this.root) {
if (value == node.value) {
target = node;
} else if (value < node.value && node.left !== null) {
parent = node;
return findValue(node.left);
} else if (value < node.value && node.left === null) {
return null;
} else if (value > node.value && node.right !== null) {
parent = node;
return findValue(node.right);
} else {
return null;
}
}.bind(this)());
if (target === null) {
return null;
}
// Count the children of the target to delete
var children =
(target.left !== null ? 1 : 0) + (target.right !== null ? 1 : 0);
// Case 1: Target has no children
if (children === 0) {
if (target == this.root) {
this.root = null;
} else {
if (parent.left == target) {
parent.left = null;
} else {
parent.right = null;
}
}
}
// Case 2: Target has one child
else if (children == 1) {
var newChild = target.left !== null ? target.left : target.right;
if (parent === null) {
target.value = newChild.value;
target.left = null;
target.right = null;
} else if (newChild.value < parent.value) {
parent.left = newChild;
} else {
parent.right = newChild;
}
target = null;
}
// Only change code below this line
// Case 3: Target has two children
else if (children === 2) {
// find the smallest value from the right side
const newChildValue = this.findMin(target.right);
// recursively remove the node with this value
this.remove(newChildValue);
// set the target value to the new child value
target.value = newChildValue;
}
};
// Find the minimum and maximum values from a tree or subtree
this.findMin = (root = this.root) => {
if (!this.root) return null;
return root.left ? this.findMin(root.left) : root.value;
}
this.findMax = (root = this.root) => {
if (!this.root) return null;
return root.right ? this.findMax(root.right) : root.value;
}
}
Link to the challenge: