450. Delete Node in a BST LeetCode Solution

In this guide, you will get 450. Delete Node in a BST LeetCode Solution with the best time and space complexity. The solution to Delete Node in a BST problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Delete Node in a BST solution in C++
Delete Node in a BST solution in Java
Delete Node in a BST solution in Python
Additional Resources

450. Delete Node in a BST LeetCode Solution image

Problem Statement of Delete Node in a BST

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

Follow up: Could you solve it with time complexity O(height of tree)?

Complexity Analysis

Time Complexity: O(h) = O(\log n)
Space Complexity: O(h) = O(\log n)

450. Delete Node in a BST LeetCode Solution in C++

class Solution {
 public:
  TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr)
      return nullptr;
    if (root->val == key) {
      if (root->left == nullptr)
        return root->right;
      if (root->right == nullptr)
        return root->left;
      TreeNode* minNode = getMin(root->right);
      root->right = deleteNode(root->right, minNode->val);
      minNode->left = root->left;
      minNode->right = root->right;
      root = minNode;
    } else if (root->val < key) {
      root->right = deleteNode(root->right, key);
    } else {  // root->val > key
      root->left = deleteNode(root->left, key);
    }
    return root;
  }

 private:
  TreeNode* getMin(TreeNode* node) {
    while (node->left != nullptr)
      node = node->left;
    return node;
  }
};
/* code provided by PROGIEZ */

450. Delete Node in a BST LeetCode Solution in Java

class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null)
      return null;
    if (root.val == key) {
      if (root.left == null)
        return root.right;
      if (root.right == null)
        return root.left;
      TreeNode minNode = getMin(root.right);
      root.right = deleteNode(root.right, minNode.val);
      minNode.left = root.left;
      minNode.right = root.right;
      root = minNode;
    } else if (root.val < key) {
      root.right = deleteNode(root.right, key);
    } else { // root.val > key
      root.left = deleteNode(root.left, key);
    }
    return root;
  }

  private TreeNode getMin(TreeNode node) {
    while (node.left != null)
      node = node.left;
    return node;
  }
}
// code provided by PROGIEZ

450. Delete Node in a BST LeetCode Solution in Python

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

  def _getMin(self, node: TreeNode | None) -> TreeNode | None:
    while node.left:
      node = node.left
    return node
 # code by PROGIEZ