Leetcode Delete Node in a BST problem solution

by

In this Leetcode Delete Node in a BST problem solution we have 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.
Leetcode Delete Node in a BST problem solution

Problem solution in Python.

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return root
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
            return root
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
            return root
        else: # root.val == key
            if not root.right:
                return root.left
            smInRight = root.right
            # Find the smallest node of right subtree of root 
            # and attach left subtree of root to left of the smallest node in right
            while smInRight.left: 
                smInRight = smInRight.left
            smInRight.left = root.left
            return root.right

Problem solution in Java.

public TreeNode deleteNode(TreeNode root, int key) {
    if(root == null)
        return root;

    if(root.val == key){
        if(root.right == null)
            return root.left;

        TreeNode curr = root.right;
        while(curr.left != null)
            curr = curr.left;
        curr.left = root.left;

        return root.right;
    }else if(root.val < key){
        root.right = deleteNode(root.right, key);
    }else{
        root.left = deleteNode(root.left, key);
    }
    return root;
}

Problem solution in C++.

class Solution {
public:
    TreeNode * deleteNode(TreeNode*& root, int key) {
        if (!root) {
            return NULL;
        }

        if (root->val == key) {
            if (root->right) {
                TreeNode* nextGt = NULL;
                findMin(root->right, nextGt);
                swap(root->val, nextGt->val);
                root->right = deleteNode(root->right, key);
                return root;
            }
            else {
                TreeNode* res = root->left;
                delete root;
                return res;
            }
        }
        else if (root->val < key) {
            root->right = deleteNode(root->right, key);
            return root;
        }
        else if (root->val > key) {
            root->left = deleteNode(root->left, key);
            return root;
        }
        else {
            return root;
        }
    }
private:
    void findMin(TreeNode* root, TreeNode*& min) {
        if(!root){
            return;
        }
        
        min = root;
        while (min && min->left) {
            min = min->left;
        }
    }
};