# 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:

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

**Algorithm:**

- If the node has no child, return null.
- If the node has only one child, we will return that non null child.
- 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;

}

}