Bottom-up Recursive Python Solution. O(log(n)) Time.


  • 8
    B

    Idea:

    1. When found the node, put right child of the node to the right of the right most leaf node of left child. That way the values are still in order.
    2. Return the left child of the node(skip root, a.k.a delete it). If the node doesn't have left child, return right child.
    3. Otherwise do binary search. If key < root.val, change left child to the returned new root. Do right child if key > root.val.

    This solution always runs in O(log(n)) time since when it finds the node to delete, it goes to the right most leaf of the left sub-tree to put right sub-tree of the node there.

    class Solution(object):
        def deleteNode(self, root, key):
            """
            :type root: TreeNode
            :type key: int
            :rtype: TreeNode
            """
            if not root: return None
            
            if root.val == key:
                if root.left:
                    # Find the right most leaf of the left sub-tree
                    left_right_most = root.left
                    while left_right_most.right:
                        left_right_most = left_right_most.right
                    # Attach right child to the right of that leaf
                    left_right_most.right = root.right
                    # Return left child instead of root, a.k.a delete root
                    return root.left
                else:
                    return root.right
            # If left or right child got deleted, the returned root is the child of the deleted node.
            elif root.val > key:
                root.left = self.deleteNode(root.left, key)
            else:
                root.right = self.deleteNode(root.right, key)
                
            return root
    

  • 0

    @boy27910231 The answer is accepted by OJ and of course is very brilliant one, but I think it has a potential to increase the height of the tree with the delete method called on.


  • 0
    B

    @Ipeq1 Yes you are right. This solution is kind of a shortcut, which messes up the tree height. But since the description doesn't require the tree remain balanced after deletion, I just went with the easy way. To maintain balanced, we still have to use the traditional way.


Log in to reply
 

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