450. Delete Node in a BST - Leetcode Solution

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            min_larger_node = self.getMin(root.right)
            root.val = min_larger_node.val
            root.right = self.deleteNode(root.right, min_larger_node.val)
        return root

    def getMin(self, node):
        while node.left:
            node = node.left
        return node

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else if (key > root->val) {
            root->right = deleteNode(root->right, key);
        } else {
            if (!root->left) return root->right;
            if (!root->right) return root->left;
            TreeNode* minNode = getMin(root->right);
            root->val = minNode->val;
            root->right = deleteNode(root->right, minNode->val);
        }
        return root;
    }
    TreeNode* getMin(TreeNode* node) {
        while (node->left) node = node->left;
        return node;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode minNode = getMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        }
        return root;
    }
    private TreeNode getMin(TreeNode node) {
        while (node.left != null) node = node.left;
        return node;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        let minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    }
    return root;

    function getMin(node) {
        while (node.left != null) node = node.left;
        return node;
    }
};

Problem Description

Given the root of a Binary Search Tree (BST) and an integer key, delete the node with value key from the BST. Return the root of the BST after deletion. If the key does not exist in the tree, return the original tree. The BST must retain its properties after deletion:

Left subtree nodes are less than the node's value
Right subtree nodes are greater than the node's value

There is only one valid way to delete the node, and you must not reuse or duplicate any node values.

Thought Process

To solve this problem, we need to understand how deletion works in a Binary Search Tree. At first glance, it can seem daunting because removing a node might break the BST structure. The main challenge is handling different cases depending on the node's children:

If the node is a leaf (no children), we simply remove it.
If the node has one child, we replace the node with its child.
If the node has two children, we need to find a replacement that keeps the BST valid. This is usually the node's in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree).

A brute-force approach might involve reconstructing the tree, but this would be inefficient. Instead, we look for a recursive solution that directly manipulates pointers, making the operation efficient and elegant.

Solution Approach

The solution uses recursion to traverse the BST, searching for the node with value key. Here's a step-by-step breakdown:

Traverse the tree: If key is less than the current node's value, we recurse on the left subtree. If greater, we recurse on the right subtree.
Node found: When we find the node with value key, there are three cases:
- No children (leaf): Return null to remove the node.
- One child: Return the non-null child to replace the node.
- Two children:
  - Find the in-order successor (smallest node in the right subtree).
  - Copy the successor's value to the current node.
  - Recursively delete the successor from the right subtree.
Return the modified tree: After deletion, return the (possibly updated) root node to maintain the tree structure.

This approach ensures the BST property is preserved at each step. Using recursion allows us to handle the tree's structure naturally.

Example Walkthrough

Let's consider a sample BST:

Suppose we want to delete key = 3.

Start at root (5). Since 3 < 5, go left to node 3.
Node 3 matches the key. Node 3 has two children (2 and 4).
Find the in-order successor: smallest node in the right subtree of 3 is 4.
Replace node 3's value with 4.
Recursively delete node 4 from the right subtree. Node 4 is a leaf, so it's simply removed.

Final tree structure:

Each step maintains the BST property, and the node with value 3 is removed.

Time and Space Complexity

Brute-force approach: Rebuilding the tree after removing a node would take O(N) time and space, where N is the number of nodes.
Optimized (recursive) approach:
- Time Complexity: O(H), where H is the height of the tree. In the worst case (unbalanced tree), H = N. In a balanced tree, H = log N.
- Space Complexity: O(H) due to recursion stack.

The optimized approach is efficient because it only traverses the path from root to the node to be deleted, and possibly to its in-order successor.

Summary

Deleting a node from a BST involves careful pointer manipulation to maintain the tree's structure and properties. By considering the three possible cases (no children, one child, two children), and using recursion to traverse and update the tree, we achieve an efficient and elegant solution. The key insight is replacing a node with two children by its in-order successor, ensuring the BST remains valid.

AlgoMap.io

Want Help Cracking FAANG?