> For the complete documentation index, see [llms.txt](https://sisyphus.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sisyphus.gitbook.io/project/leetcode-notes/binary-search-tree/450.-delete-node-in-a-bst.md).
# 450. 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:
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
```
Deletion is more complicated than the two operations we mentioned before. There are also many different strategies for deletion. We are going to introduce one of them which minimizes the changes. Our solution is to replace the target node with a proper child. According to the number of its children, we should consider three different cases:1. If the target node has ***no child***, we can simply remove the node.\
2\. If the target node has ***one child***, we can use its child to replace itself.\
3\. If the target node has ***two children***, replace the node with its in-order successor or predecessor node and delete that node.
Here are examples of different cases to help you understand this strategy.
By understanding the strategy above, you should be able to implement deletion function on your own. We have done an exercise about finding the inorder successor in a BST in the previous section. The solution for that question might help you implement the deletion function.
```python
# 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):
if not root: # for the first root, if it is None, return None.
return None
# Modify either root, root.left or root.right and return the modified root
if key < root.val:
root.left = self.deleteNode(root.left, key) # neet to reassign the returned root to the proper child
elif key > root.val:
root.right = self.deleteNode(root.right, key) # neet to reassign the returned root to the proper child
else: # found the target root
if not root.left and not root.right: # target root has no children
return None
elif not root.left: # target root has RIGHT child, replace root with the RIGHT child
return root.right
elif not root.right: # target root has LEFT child, replace root with the LEFT child
return root.left
else: # When root has both left and right children
# Find the successor, replace root.val with successor.val, deleteNode(successor).
# In this way, we don't need to know the parent of target root to delete the target root.
successor = self.findSuccessorInRightChild(root) # Since currently root mush have left and right child, we only need to find the successor in the RIGHT child branch. This would be easier compared to maintain a stack of successors, which is sepcifically designed to find both the right child successor and successor in the other part of the tree.
root.val = successor.val # replace root value with successor value will help us not thinking to much about the parent root of the target root / successor(since successor also need to be deleted and it will be the target root for the next recursive loop).
'''
This is WROING!!!!
We should modify root / root.left / root.right and return root, not return deleteNode(succesor, successor.val)
Only return None when the root should be None (if not root.left and not root.right: return None)
'''
# return self.deleteNode(, successor.val) # recursively delete
'''
Wrong anwser ends
'''
root.right = self.deleteNode(root.right, successor.val)
return root
def findSuccessorInRightChild(self, root):
cur = root.right
while(cur.left):
cur = cur.left
return cur
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## 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://sisyphus.gitbook.io/project/leetcode-notes/binary-search-tree/450.-delete-node-in-a-bst.md?ask=
```
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.