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.

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.

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.

  1. If the node is found, delete the node.
  1. If the node has only one child, we will return that non null child.
  2. If the node has two child, then we will replace the curr node with the node that has maximum value in its left subtree.
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;
}
}