High order binary search tree

1. Binary search tree is also called binary sort tree , It could be an empty tree , Or a binary tree with the following properties :
（1） If its left subtree is not empty , Then the values of all nodes on the left subtree are smaller than the values of the root nodes
（2） If its right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of the root node
（3） Its left and right subtrees are also binary search trees

2. Implementation of binary search tree

class BSNode {
    
    public int val;
    public BSNode left;
    public BSNode right;

    public BSNode() {
    
    }

    public BSNode(int val) {
    
        this.val = val;
    }
    public BSNode root = null;

    public boolean insert(int val) {
    
        BSNode node = new BSNode(val);
        if(root == null) {
    
            root = node;
            return true;
        }
        BSNode cur = root;
        BSNode par = null;
        while (cur != null) {
    
            if(cur.val == val) {
    
                return false;
            } else if (cur.val > val){
    
                par = cur;
                cur = cur.left;
            } else {
    
                par = cur;
                cur = cur.right;
            }
        }
        if(par.val > val) {
    
            par.left = node;
        } else {
    
            par.right = node;
        }
        return true;
    }

    public boolean search(int val) {
    
        if(root == null) return false;
        BSNode cur = root;
        while (cur != null) {
    
            if(cur.val == val) {
    
                return true;
            } else if(cur.val > val) {
    
                cur = cur.left;
            } else {
    
                cur = cur.right;
            }
        }
        return false;
    }
    public void remove(int val) {
    
        if(root == null) return;
        BSNode cur = root;
        BSNode pre = null;
        while (cur != null) {
    
            if(cur.val == val) {
    
                // Delete operation 
                removeNode(val,pre,cur);
            } else if (cur.val > val) {
    
                pre = cur;
                cur = cur.left;
            } else {
    
                pre = cur;
                cur = cur.right;
            }
        }
    }
    public void removeNode(int val, BSNode pre, BSNode cur) {
    
        if(cur.left == null) {
    
            if (root == cur) {
    
                root = cur.right;
            } else if(cur == pre.left){
    
                pre.left = cur.right;
            } else if (cur == pre.right) {
    
                pre.right = cur.right;
            }
        } else if (cur.right == null) {
    
            if(root == cur) {
    
                root = cur.left;
            } else if(cur == pre.left) {
    
                pre.left = cur.left;
            } else if (cur == pre.right) {
    
                pre.right = cur.left;
            }
        } else {
    
            BSNode targetParent = cur;
            BSNode target = cur.right;
            while (target.left != null) {
    
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
    
                targetParent.left = target.right;
            } else {
    
                targetParent.right = target.right;
            }
        }
    }
}

public class BST1 {
    
    public static void preOrder(BSNode root) {
    
        if(root != null) {
    
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    public static void inOrder(BSNode root) {
    
        if(root != null) {
    
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
    }
    public static void postOrder(BSNode root) {
    
        if(root != null) {
    
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }
    }
    public static void main(String[] args) {
    
        BSNode bsNode = new BSNode();
        bsNode.insert(4);
        bsNode.insert(3);
        bsNode.insert(1);
        bsNode.insert(15);
        preOrder(bsNode.root);
        System.out.println();
        System.out.println(bsNode.search(3));
        System.out.println(bsNode.search(2));
        bsNode.remove(1);
        preOrder(bsNode.root);
    }
}