← All posts

Data Structures / Binary Search Tree/Delete node

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;
}