# Data Structures / Binary Search Tree/Delete node

Posted On 12.30.2021

Algorithm to delete a node from a BST:

• Find the node to delete
• Find the deepest right most (DRM) node of the tree
• Replace the node to delete with the DRM
• Continue find and delete the DRM in the tree

Implementation:

delete(value: number) {
this.root = this.deleteAt(value, this.root);
}

private deleteAt(value: number, node?: TreeNode): TreeNode | undefined {
if (node) {
if (value < node.value) {
node.left = this.deleteAt(value, node.left);
} else if (value > node.value) {
node.right = this.deleteAt(value, node.right);
} else {
if (!node.left && !node.right) {
// case 1: node has no child
node = undefined;
} else if (node.left && node.right) {
// case 2: node has two child
let rightMost = this.deepestRightMost();
if (rightMost) {
node.value = rightMost.value;
node.left = this.deleteAt(rightMost.value, node.left);
node.right = this.deleteAt(rightMost.value, node.right);
}
} else {
// case 3: node has 1 child
node = node.left || node.right;
}
}
}
return node;
}