# Delete node from 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:

1. Search for a node to remove.
2. 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
```

```
# 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 not root:
            return None

        node, parent = self.lookup(root, key)
        if not node: # some node, which does not even exist in the BST. just return top root
            return root

        '''
        if node:
            print 'node: ', node.val
        if parent:
            print 'parent: ', parent.val
        '''    
        #//////////////////////////////////////////////////////////
        # Case 1: Leaf node. both right = left = None
        #//////////////////////////////////////////////////////////
        if node.right == node.left == None:
            if parent:
                if parent.left == node:
                    parent.left = None
                else:
                    parent.right = None
            else: # top root node having 0 chidren
                return None

        #//////////////////////////////////////////////////////////
        # Case 2: The node has only 1 child
        #//////////////////////////////////////////////////////////
        elif (node.left and node.right is None) or (node.right and node.left is None):
            if parent:
                if parent.left == node:
                    if node.left:
                        parent.left = node.left
                    else:
                        parent.left = node.right
                else:
                    if node.left:
                        parent.right = node.left
                    else:
                        parent.right = node.right
            else: # top root node having only 1 child
                if node.left:
                    node = node.left
                else:
                    node = node.right

                root = node

        #//////////////////////////////////////////////////////////
        # Case 3: The node has both children - complex case
        #//////////////////////////////////////////////////////////
        elif node.right and node.left:
            p = node
            successor = node.right
            while successor.left:
                p = successor
                successor = successor.left

            # At this stage: reached the leftmost leaf node of the right subtree
            # copy data of successor to node
            node.val = successor.val
            if p.left == successor:
                p.left = successor.right
            else:
                p.right = successor.right


        return root

    #//////////////////////////////////////////////////////////
    # function lookup: Also note, how the parent node is being sent back        
    #//////////////////////////////////////////////////////////
    def lookup(self, root, key, parent=None):

        if not root:
            return None, None

        if key == root.val:
            return root, parent
        elif key < root.val:
            return self.lookup(root.left, key, root)
        else:
            return self.lookup(root.right, key, root)
```

Ref: <http://www.laurentluce.com/posts/binary-search-tree-library-in-python/comment-page-1/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://bhabs.gitbook.io/prepbook/coding/delete-node-from-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.