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

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Ready for the BTC to BSC bridge? Swingby just made running a Metanode even better.

Top 5 lead generation tools

Software Entropy and Gardening

Humanoid Soccer Shooter — Endgame (3/3)

Robotis OP3 in action

What a Cluster: Deployment using Kubernetes and Helm

Alexa, tell Stackery to deploy

The Foobar challenge: Google’s hidden test for developers

Six Benefits of Integrating ERP with Salesforce CRM

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abhinay Gupta

Abhinay Gupta

More from Medium

A primer on Recursive algorithms

DSA #5 Two Pointers Technique

Program a Linked List with Templates in C++

Algorithms