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).
Example: 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
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/delete-node-in-a-bst ## Basic Ideas: Find the target ## If the target is a leaf, we need the parent node ## If the target only have one child ## If the target has both children ## ## Complexity: Time O(h), Space O(1) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ if root is None: return None # delete root if root.val == key: # root is a leaf if root.left is None and root.right is None: return None else: self.deleteRootNode(root, None) return root # delete node inside the tree prev, node = root, root while node: if node.val == key: break prev = node if node.val > key: node = node.left else: node = node.right # node is the target to be deleted if node: self.deleteRootNode(node, prev) return root def deleteRootNode(self, root, prev): if root is None: return # leaf if root.left is None and root.right is None: if root == prev.left: prev.left = None else: prev.right = None return if root.left: # find the largest item in the left right p, node = root, root.left while node.right: p = node node = node.right # swap value root.val = node.val return self.deleteRootNode(node, p) if root.right: p, node = root, root.right while node.left: p = node node = node.left root.val = node.val return self.deleteRootNode(node, p)