Skip to content

450. Delete Node in a BST 👍

  • Time: $O(h) = O(\log n)$
  • Space: $O(h) = O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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