> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/2.binary-tree/87remove-node-in-binary-search-tree.md).

# 87.Remove Node in Binary Search Tree

## 1.Description(Hard)

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

**Example**

Given binary search tree:

```
    5
   / \
  3   6
 / \
2   4
```

Remove 3, you can either return:

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

or

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

## 2.Code

<https://lefttree.gitbooks.io/leetcode/binaryTree/removeNodeInBST.html>

Delete node 有三种情况

因为要delete,在find这个node的过程中要保留一个parent的变量

1. leaf node

删掉这个node，把parent对这个node的reference设为null

1. Node with only one child

delete the node,把parent对node的reference link到node的child

1. Node with 2 children
   * find the minimum node of right subtree
   * replace the value of found node
   * delete the old duplicate node(case 1/2, cause minimum node should not have left child)

<http://www.cnblogs.com/grandyang/p/6228252.html>