# Delete a Node with Two Children in a Binary Search Tree

## Hints

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.

## Solutions

Solution 1 (Click to Show/Hide)
``````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;
// Only change code below this line
this.remove = function(value) {
if (!this.root) return null;

// find the node
let parent;
let target = this.root;
while (target && target.value !== value) {
parent = target;
if (target.value > value) {
target = target.left;
} else {
target = target.right;
}
}
if (!target) return null;

// remove the node
// -- zero or one children
if (!(target.left && target.right)) {
// ---- root node
const replacement = target.right ? target.right : target.left;
if (!parent) {
this.root = replacement;
} else {
// ---- other node
const direction = parent.left === target ? "left" : "right";
parent[direction] = replacement;
}
} else {
// -- two children
// ---- replace current value with smallest child
const newChildValue = this.findMin(target.right);
this.remove(newChildValue);
target.value = newChildValue;
}
}

this.findMin = function(node = this.root) {
if (!node) return null;
return node.left ? this.findMin(node.left) : node.value;
}

this.findMax = function(node = this.root) {
if (!node) return null;
return node.right ? this.findMax(node.right) : node.value;
}
}
``````
3 Likes