Insertion, Search and Deletion in BST

Insertion:

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Code:

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            return node;
        }
        //p->parent q-> current node
        TreeNode p = null, q= root;
        while(q != null) {
            p = q;
            if(q.val > val) {
                q = q.left;
            } else {
                q = q.right;
            }
        }
        if(p.val > val) {
            p.left = node;
        } else {
            p.right = node;
        }
        return root;
    }
}

Search:

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Code:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null){
            return null;
        }
        
        if(root.val<val) return searchBST(root.right,val);
        if(root.val>val) return searchBST(root.left,val);
        return root;
    }
}

Deletion:

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Algorithm:

1. If the node has no child, return null.
2. If the node has only one child, we will return that non null child.
3. If the node has two child, then we will replace the curr node with the node that has maximum value in its left subtree.

Code:

class Solution {
    public TreeNode deleteNode(TreeNode root, int val) {
        if(root==null) return null;
        if(val>root.val){
            root.right= deleteNode(root.right,val);
        }
        else  if(val<root.val){
            root.left= deleteNode(root.left,val);
        }
        else{
            if(root.left!=null&&root.right!=null){
                int maxm= max(root.left);
                root.val= maxm;
                root.left= deleteNode(root.left,maxm);
            }
            else if(root.left!=null){
                return root.left;
            }
            else if (root.right!=null){
                return root.right;
            }
            else{
                return null;
            }
        }
        return root;
    }
    public int max(TreeNode root){
        if(root.right!=null){
            return max(root.right);
        }
        else return root.val;
    }
}