Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].
-105 <= Node.val <= 105
Each node has a unique value.
root is a valid binary search tree.
-105 <= key <= 105

🤓Explanation

Okay, imagine you have a special kind of family tree (a Binary Search Tree) where everyone is organized by age. Younger people are always on the left side of their parent, and older people are always on the right.

You want to remove someone from this family tree based on their age (the 'key').

1 - Finding the Person to Remove (traverseBST):

Start at the very top of the family tree (the 'root').
If the tree is empty, the person isn't there. Stop.
If the person at the current spot is the one you want to remove, remember this person and who their parent is. Stop this part.
If the age you're looking for is younger than the person at the current spot, go look on their left side (their younger relatives). Repeat this process.
If the age you're looking for is older than the person at the current spot, go look on their right side (their older relatives). Repeat this process.

2 - Removing the Person (deleteNode):

First, did you even find the person in step 1? If not, the family tree stays the same.

Case 1: The person has no children (no one younger or older directly related to them):

If this person was the very top of the tree, now the tree is empty.
Otherwise, go to their parent. If the person you removed was on their left, tell the parent they no longer have a left child. If they were on the right, tell the parent they no longer have a right child.

Case 2: The person has only one child (either younger OR older):

If this person was the very top of the tree, their only child now becomes the new top of the tree.
Otherwise, go to their parent. If the person you removed was on their left, now their only child takes their place as the left child. If they were on their right, their only child takes their place as the right child.

Case 3: The person has two children (both younger AND older):

You need to find someone to take their place who keeps the family tree organized. A good choice is the "oldest" person in their younger relatives (the rightmost person on their left side) OR the "youngest" person in their older relatives (the leftmost person on their right side). The code here uses the "youngest" in their older relatives.
Find this "youngest" person on the right side.
Copy their age and other information to the spot of the person you wanted to remove.
Now, you still have the "youngest" person in their original spot on the right side. You need to remove them using one of the cases above (they will likely have zero or one child in this situation).

3 - The Result:

After doing all this, you have a (possibly) updated family tree, and you return the top of the tree.

Simplified Analogy:

Imagine removing a book from a sorted bookshelf.

If the book is at the end, you just take it off.
If the book has other books leaning on it from one side, the books on that side just shift to fill the gap.
If the book has books leaning on it from both sides, you might take the very next book in the shelf (either just before or just after it in alphabetical order), put it in the empty spot, and then remove the book you just moved from its original spot. This keeps the bookshelf sorted.

🤓Implementations

🐍Python

# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def traverseBST(self, parent: Optional[TreeNode], root: Optional[TreeNode], key: int) -> (Optional[TreeNode], Optional[TreeNode]):
        """
        Traverses the Binary Search Tree (BST) to find the node with the given key and its parent.

        Args:
            parent (Optional[TreeNode]): The parent node of the current node being examined. Initially None.
            root (Optional[TreeNode]): The current node being examined in the BST.
            key (int): The value of the node to search for.

        Returns:
            Tuple[Optional[TreeNode], Optional[TreeNode]]: A tuple containing the parent node and the found node (or None if not found).
        """
        if not root:
            return (None, None)  # Key not found in the subtree

        # Found the node with the target key
        if key == root.val:
            return (parent, root)

        # If the key is less than the current node's value, go to the left subtree
        if key < root.val:
            return self.traverseBST(root, root.left, key)
        # If the key is greater than the current node's value, go to the right subtree
        else:
            return self.traverseBST(root, root.right, key)

    def findMin(self, node: TreeNode) -> TreeNode:
        """
        Finds the node with the minimum value in a given subtree.
        This is done by traversing as far left as possible.

        Args:
            node (TreeNode): The root of the subtree to search in.

        Returns:
            TreeNode: The node with the minimum value in the subtree.
        """
        while node.left:
            node = node.left
        return node

    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        """
        Deletes a node with the given key from the Binary Search Tree (BST).

        Args:
            root (Optional[TreeNode]): The root of the BST.
            key (int): The value of the node to delete.

        Returns:
            Optional[TreeNode]: The root of the BST after deletion (may be updated).
        """
        # Find the node to delete and its parent
        parent, node_to_delete = self.traverseBST(None, root, key)

        # If the node to delete is not found, return the original root
        if not node_to_delete:
            return root  # Key not found

        # Case 1: Node to delete has no children (it's a leaf node)
        if not node_to_delete.left and not node_to_delete.right:
            # If the node to delete is the root
            if not parent:
                return None  # The tree becomes empty
            # If the node to delete is a left child of its parent
            elif key < parent.val:
                parent.left = None
            # If the node to delete is a right child of its parent
            else:
                parent.right = None

        # Case 2: Node to delete has only a left child
        elif not node_to_delete.right:
            # If the node to delete is the root
            if not parent:
                return node_to_delete.left
            # If the node to delete is a left child of its parent
            elif key < parent.val:
                parent.left = node_to_delete.left
            # If the node to delete is a right child of its parent
            else:
                parent.right = node_to_delete.left

        # Case 3: Node to delete has only a right child
        elif not node_to_delete.left:
            # If the node to delete is the root
            if not parent:
                return node_to_delete.right
            # If the node to delete is a left child of its parent
            elif key < parent.val:
                parent.left = node_to_delete.right
            # If the node to delete is a right child of its parent
            else:
                parent.right = node_to_delete.right

        # Case 4: Node to delete has two children
        else:
            # Find the inorder successor (the smallest node in the right subtree)
            successor = self.findMin(node_to_delete.right)
            # Replace the value of the node to delete with the value of the successor
            node_to_delete.val = successor.val
            # Recursively delete the successor from the right subtree
            # This is done because the successor is now in the position of the deleted node
            node_to_delete.right = self.deleteNode(node_to_delete.right, successor.val)

        return root

🟦Typescript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * val: number
 * left: TreeNode | null
 * right: TreeNode | null
 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 * }
 */

/**
 * Given a root node reference of a BST and a key, delete the node with the given key in the BST.
 * Return the root node reference (possibly updated) of the BST.
 *
 * Basically, the deletion can be divided into two stages:
 * 1. Search for a node to remove.
 * 2. If the node is found, delete the node.
 *
 * @param {TreeNode | null} root The root of the Binary Search Tree.
 * @param {number} key The value of the node to delete.
 * @returns {TreeNode | null} The root of the BST after deletion (may be updated).
 */
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    /**
     * Helper function to traverse the BST and find the node with the given key and its parent.
     *
     * @param {TreeNode | null} parent The parent node of the current node being examined. Initially null.
     * @param {TreeNode | null} root The current node being examined in the BST.
     * @param {number} key The value of the node to search for.
     * @returns {[TreeNode | null, TreeNode | null]} A tuple containing the parent node and the found node (or null if not found).
     */
    function traverseBST(parent: TreeNode | null, root: TreeNode | null, key: number): [TreeNode | null, TreeNode | null] {
        if (!root) {
            return [null, null]; // Key not found in the subtree
        }

        // Found the node with the target key
        if (key === root.val) {
            return [parent, root];
        }

        // If the key is less than the current node's value, go to the left subtree
        if (key < root.val) {
            return traverseBST(root, root.left, key);
        }
        // If the key is greater than the current node's value, go to the right subtree
        else {
            return traverseBST(root, root.right, key);
        }
    }

    /**
     * Helper function to find the node with the minimum value in a given subtree.
     * This is done by traversing as far left as possible.
     *
     * @param {TreeNode} node The root of the subtree to search in.
     * @returns {TreeNode} The node with the minimum value in the subtree.
     */
    function findMin(node: TreeNode): TreeNode {
        while (node.left) {
            node = node.left;
        }
        return node;
    }

    // Find the node to delete and its parent
    const [parent, nodeToDelete] = traverseBST(null, root, key);

    // If the node to delete is not found, return the original root
    if (!nodeToDelete) {
        return root; // Key not found
    }

    // Case 1: Node to delete has no children (it's a leaf node)
    if (!nodeToDelete.left && !nodeToDelete.right) {
        // If the node to delete is the root
        if (!parent) {
            return null; // The tree becomes empty
        }
        // If the node to delete is a left child of its parent
        else if (key < parent.val) {
            parent.left = null;
        }
        // If the node to delete is a right child of its parent
        else {
            parent.right = null;
        }
    }
    // Case 2: Node to delete has only a left child
    else if (!nodeToDelete.right) {
        // If the node to delete is the root
        if (!parent) {
            return nodeToDelete.left;
        }
        // If the node to delete is a left child of its parent
        else if (key < parent.val) {
            parent.left = nodeToDelete.left;
        }
        // If the node to delete is a right child of its parent
        else {
            parent.right = nodeToDelete.left;
        }
    }
    // Case 3: Node to delete has only a right child
    else if (!nodeToDelete.left) {
        // If the node to delete is the root
        if (!parent) {
            return nodeToDelete.right;
        }
        // If the node to delete is a left child of its parent
        else if (key < parent.val) {
            parent.left = nodeToDelete.right;
        }
        // If the node to delete is a right child of its parent
        else {
            parent.right = nodeToDelete.right;
        }
    }
    // Case 4: Node to delete has two children
    else {
        // Find the inorder successor (the smallest node in the right subtree)
        const successor = findMin(nodeToDelete.right);
        // Replace the value of the node to delete with the value of the successor
        nodeToDelete.val = successor.val;
        // Recursively delete the successor from the right subtree
        // This is done because the successor is now in the position of the deleted node
        nodeToDelete.right = deleteNode(nodeToDelete.right, successor.val);
    }

    return root;
}

🐭Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 * Val int
 * Left *TreeNode
 * Right *TreeNode
 * }
 */

/**
 * Given a root node reference of a BST and a key, delete the node with the given key in the BST.
 * Return the root node reference (possibly updated) of the BST.
 *
 * Basically, the deletion can be divided into two stages:
 * 1. Search for a node to remove.
 * 2. If the node is found, delete the node.
 *
 * @param root *TreeNode The root of the Binary Search Tree.
 * @param key int The value of the node to delete.
 * @return *TreeNode The root of the BST after deletion (may be updated).
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
 /**
  * Helper function to traverse the BST and find the node with the given key and its parent.
  *
  * @param parent *TreeNode The parent node of the current node being examined. Initially nil.
  * @param root *TreeNode The current node being examined in the BST.
  * @param key int The value of the node to search for.
  * @return [*TreeNode, *TreeNode] A slice containing the parent node and the found node (or nil if not found).
  */
 var traverseBST func(parent *TreeNode, root *TreeNode, key int) (*TreeNode, *TreeNode)
 traverseBST = func(parent *TreeNode, root *TreeNode, key int) (*TreeNode, *TreeNode) {
  if root == nil {
   return nil, nil // Key not found in the subtree
  }

  // Found the node with the target key
  if key == root.Val {
   return parent, root
  }

  // If the key is less than the current node's value, go to the left subtree
  if key < root.Val {
   return traverseBST(root, root.Left, key)
  } else {
   // If the key is greater than the current node's value, go to the right subtree
   return traverseBST(root, root.Right, key)
  }
 }

 /**
  * Helper function to find the node with the minimum value in a given subtree.
  * This is done by traversing as far left as possible.
  *
  * @param node *TreeNode The root of the subtree to search in.
  * @return *TreeNode The node with the minimum value in the subtree.
  */
 var findMin func(node *TreeNode) *TreeNode
 findMin = func(node *TreeNode) *TreeNode {
  for node.Left != nil {
   node = node.Left
  }
  return node
 }

 // Find the node to delete and its parent
 parent, nodeToDelete := traverseBST(nil, root, key)

 // If the node to delete is not found, return the original root
 if nodeToDelete == nil {
  return root // Key not found
 }

 // Case 1: Node to delete has no children (it's a leaf node)
 if nodeToDelete.Left == nil && nodeToDelete.Right == nil {
  // If the node to delete is the root
  if parent == nil {
   return nil // The tree becomes empty
  }
  // If the node to delete is a left child of its parent
  if key < parent.Val {
   parent.Left = nil
  } else {
   // If the node to delete is a right child of its parent
   parent.Right = nil
  }
 } else if nodeToDelete.Right == nil {
  // Case 2: Node to delete has only a left child
  // If the node to delete is the root
  if parent == nil {
   return nodeToDelete.Left
  }
  // If the node to delete is a left child of its parent
  if key < parent.Val {
   parent.Left = nodeToDelete.Left
  } else {
   // If the node to delete is a right child of its parent
   parent.Right = nodeToDelete.Left
  }
 } else if nodeToDelete.Left == nil {
  // Case 3: Node to delete has only a right child
  // If the node to delete is the root
  if parent == nil {
   return nodeToDelete.Right
  }
  // If the node to delete is a left child of its parent
  if key < parent.Val {
   parent.Left = nodeToDelete.Right
  } else {
   // If the node to delete is a right child of its parent
   parent.Right = nodeToDelete.Right
  }
 } else {
  // Case 4: Node to delete has two children
  // Find the inorder successor (the smallest node in the right subtree)
  successor := findMin(nodeToDelete.Right)
  // Replace the value of the node to delete with the value of the successor
  nodeToDelete.Val = successor.Val
  // Recursively delete the successor from the right subtree
  // This is done because the successor is now in the position of the deleted node
  nodeToDelete.Right = deleteNode(nodeToDelete.Right, successor.Val)
 }

 return root
}

If you liked this content I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.

Muchas gracias!

Follow me for more content like this.

Down below you can find other ways to tip my work.

BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"

DSA (Medium) - Binary Search Tree - Delete Node in a BST (Python, Typescript & Go)

🤓Explanation

🤓Implementations

🐍Python

🟦Typescript

🐭Go