# Tree - 450. Delete Node in a BST

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

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

go：

``````/**

* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func deleteNode(node *TreeNode, key int) *TreeNode {
if node == nil {
return nil
}

if key < node.Val {
node.Left = deleteNode(node.Left, key)
return node
} else if key > node.Val {
node.Right = deleteNode(node.Right, key)
return node
} else { // key == node.Val
// 1. 左子树为空
if node.Left == nil {
rightNode := node.Right
node.Right = nil
return rightNode
}

// 2. 右子树为空
if node.Right == nil {
leftNode := node.Left
node.Left = nil
return leftNode
}

// 3. 左右子树都不为空
// 找到待删除的节点的后继（比待删除节点的最小节点），然后用这个后继代替待删除的节点. Hibbard deletion
successor := minimum(node.Right)
successor.Right = removeMinNode(node.Right)
successor.Left = node.Left
return successor
}
}

// 以root为根的bst的最小值
func minimum(root *TreeNode) *TreeNode {
if root.Left == nil {
return root
}
return minimum(root.Left)
}

// 删除以root为根的bst的最小值，并返回这个位置应该变成的节点
func removeMinNode(node *TreeNode) *TreeNode {
if node.Left == nil {
rightNode := node.Right
node.Right = nil
return rightNode
}

node.Left = removeMinNode(node.Left)
return node
}
``````

Nothing just happens, it's all part of a plan.