# python - delete node in BST

• ``````# 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

``````

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