## Delete a node from BST in java

You are given N nodes and have to form BST from it.You are given a key K, delete node with value K.
Note: If K is not present in the BST, do not modify the BST.

### Input Format

The first line inputs N, the number of nodes and K, key.
The second line inputs the value of N nodes of the BST.

### Output Format

Print the preorder traversal of the updated BST in a new line.

### Example

Input

```7 42
2 81 42 87 90 41 66
```

Output

```2 81 66 41 87 90
```

Explaination

```     2
\
81
/  \
42    87
/  \    \
41   66   90

As 42 is present in the given nodes, so the node 42 will deleted and the updated tree will be like

2
\
81
/  \
66    87
/       \
41       90

The preorder will be 2 81 66 41 87 90.
```

### Constraints:

1 <= N <= 1000
-1000 <= Val[node],K <= 1000

## Solution of Delete a node from BST in java:–

```import java.util.*;
import java.lang.*;
import java.io.*;

class Node{
int val;
Node left, right;
Node(int val){
this.val = val;
left = null;
right = null;
}
}
class BST{
Node root;
BST(){
root = null;
}
Node insert(Node node, int val){
if(node==null){
node = new Node(val);
return node;
}
if(val<node.val){
node.left = insert(node.left, val);
}else{
node.right = insert(node.right, val);
}
return node;
}
int minValue(Node node){
int minv = node.val;
while(node.left!=null){
node = node.left;
minv = node.val;
}
return minv;
}
Node delete(Node node, int k){
if(node==null)return node;
else if(k<node.val){
node.left = delete(node.left,k);
}else if(k>node.val){
node.right = delete(node.right,k);
}else{
if(node.left==null)return node.right;
else if(node.right==null)return node.left;
node.val = minValue(node.right);
node.right = delete(node.right, node.val);
}
return node;
}
void preOrderTraversal(Node node){
if(node==null)
return;
System.out.print(node.val + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
public class Main{
public static void main (String[] args) throws java.lang.Exception
{
//your code here
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
BST tree = new BST();
for(int i=0;i<n;i++){
tree.root = tree.insert(tree.root, sc.nextInt());
}
tree.root = tree.delete(tree.root, k);
tree.preOrderTraversal(tree.root);
}}```