# 450. 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.
Note: Time complexity should be O(height of tree).
root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 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 following BST. 5 / \ 4 6 / \ 2 7 Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7
Approach 1: iterative.
Approach 2: recursive.
# Code (Python)
def deleteNode(self, root, key): # iterative node = root parent = TreeNode(0) parent.right = root anchor = parent # search for the node while node: if node.val == key: break elif node.val < key: parent = node node = node.right else: parent = node node = node.left # node not found if not node: return root # node is a leaf -- just delete the node if not node.left and not node.right: if parent.left == node: parent.left = None else: parent.right = None # node has one child -- move its subtree up elif not node.left or not node.right: if parent.left == node: parent.left = node.left if node.left else node.right else: parent.right = node.left if node.left else node.right # node has 2 children -- replace with inorder successor and delete successor else: # find inorder successor successor = node.right successor_parent = node while successor.left: successor_parent = successor successor = successor.left # exchange the values node.val = successor.val successor.val = key # delete the successor --be careful that successor might have a right child if successor_parent.right == successor: successor_parent.right = successor.right else: successor_parent.left = successor.right return anchor.right
def deleteNode(self, root, key): # recursive if not root: return None 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: # this happens when root.val == key, need to delete the root if not root.left: return root.right if not root.right: return root.left # find successor node = root.right while node.left: node = node.left # the successor takes over the root's left subtree, and the new root is now root.right node.left = root.left return root.right
# Code (C++)