python - delete node in BST


  • 0
    S
    # 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
            """
    
            prev, curr = None, root
            
            # 1. find the node
            while curr and curr.val != key:
                prev = curr
                curr = curr.left if key < curr.val else curr.right
    
            
            # 2. check if node exists
            if curr is None:
                return root
            
            # 3. check if there exists a successor to the node
            if curr.right is None:
                # 4. check if the node is the root
                if curr is root:
                    return root.left
                
                # node is internal to the tree
                if prev.left is curr:
                    prev.left = curr.left
                else:
                    prev.right = curr.left
                        
                curr.left = None
                return root
    
            # 5. find inorder successor
            prev_succ, succ = curr, curr.right
            while succ.left:
                prev_succ = succ
                succ = succ.left
            
            # 6. swap the values
            curr.val = succ.val
            
            # 7. handle the right child of the successor
            if prev_succ is curr:
                prev_succ.right = succ.right
            else:
                prev_succ.left = succ.right
                
            succ.right = None
            
            return root
                            
                    
                    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.