### Delete a node from BST

##### Given a Binary Search Tree (BST) and a node no ‘x’ , your task is to delete the node ‘x’ from the BST

**Solution:**

- If its a leaf node set null.
- If it has only one child then set parent to grandchild.
- If its has two children then find inOrder successor or predecessor of that node.

##### Algorithm:

- If
`node is null`

then,`return null`

- If
`node.data < key`

then,`node.right = recursively call for right child`

- Else If
`node.data > key`

then,- node.left = recursively call for left child

- Else
- If node is left node then
- return null

- Else If node has only one child then,
- return child

- Else
`InOrderSuccessorNode = Get InOrder Successor node`

`node.data = InOrderSuccessorNode.data`

`node.right = recursively call for right child with InOrderSuccessorNode.data as key`

- If node is left node then
- Return node

Latest Source Code:

Github: BinarySearchTreeDeleteNode.java

**Output:**

50 / \ / \ 30 70 / \ / \ 20 40 60 80 --------------------------------------------------------- After delete 50 : 60 / \ / \ 30 70 / \ \ 20 40 80 --------------------------------------------------------- After delete 20 : 60 / \ / \ 30 70 \ \ 40 80