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);
}}