# Delete Node in a BST

## Question ([LC.450](https://leetcode.com/problems/delete-node-in-a-bst/))

> Given the root of a BST and a key to delete, return the root of the tree with the key deleted. 

## Example 

```
I: root = [5,3,6,2,4,null,7], key = 3

       5
     /   \ 
    3     6 
  /   \    \ 
 2     4    7

O: [5,4,6,2,null,null,7] or [5,2,6,null,4,null,7] 

promote from left subtree 

       5
     /   \ 
    2     6 
     \     \ 
      4     7

promote from right subtree 

       5
     /   \ 
    4     6 
  /        \ 
 2          7
 
```

Note: The replacing node has to be the largest from the left subtree or the smallest from the right subtree. The immediate child won't work. Check out deleting 5 for example. 

## Analysis 

Deletion is an O(h) operation in BST. That means cannot divide and conquer 2 subtrees. We can only recurse down one path. So simply inserting the entire subtree won't work. We have to promote the next up median value to replace the current root. 

## D\&C Code 

If you can do the insertion with D\&C, then deletion can be done in the same way. 

```python
def findLargest(self, root: TreeNode) -> TreeNode:

    if root is None:
        return None 
    
    if root.right is not None:
        return self.findLargest(root.right)
    else:
        return root 

def findSmallest(self, root: TreeNode) -> TreeNode:
    
    if root is None:
        return None 
    
    if root.left is not None:
        return self.findSmallest(root.left)
    else:
        return root 


def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
    
    # base 
    
    if root is None:
        return None
    
    
    # divide 
    
    if key == root.val:
        
        # perform deletion
        
        
        # 3 cases 
        
        if root.left is None and root.right is None:
            return None
        
        if root.left is None and root.right is not None:
            return root.right 
        
        if root.left is not None and root.right is None:
            return root.left 
        
        # promote largest in the left subtree 
        # or the smallest in the right subtree 
        
        # largest_left_tree = self.findLargest(root.left)    
        # root.val = largest_left_tree.val 
        # root.left = self.deleteNode(root.left, largest_left_tree.val)
                
        smallest_right_tree = self.findSmallest(root.right)
        root.val = smallest_right_tree.val 
        root.right = self.deleteNode(root.right, smallest_right_tree.val)
        
        # return the promoted subtree 
        return root 
        
        
    elif key < root.val:
        
        root.left = self.deleteNode(root.left, key)
        
        return root
    else: # k > root.val
        
        root.right = self.deleteNode(root.right, key)
    
        return root 

```

## Complexity&#x20;

Time - 2 parts searching the delete key and searching for the replacement value. The worst case is something like this&#x20;

```
                      20 
                     /  \
                    5    25
                        /  \ 
                      (22)  30 
                              \ 
                               35
                              /   \
                            34     40 
                            
```

Say we want to delete 20 and using the smallest on the right subtree replacement strategy. If 22 exists, then we just delete it and it is a leaf node. The worst case is that the next node is the smallest node. Then we have to cascade the delete to 25, to 30, 35, and eventually a leaf node. The base case for the deletion is O(1). Finding the replacement value and cascading the delete will be the height of the tree. Therefore, O(h).&#x20;

Space - Find the smallest or largest value in BST can be done without recursion. The pure deletion is just O(h).&#x20;


---

# 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://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/binary_search_tree/delete-node-in-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.