L44. Delete a Node in Binary Search Tree | BST | C++ | Java

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

Hi, hope you are well.


Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL and many other time saving features under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing yourself.

[ImpressLabs]

Remember to take delete the node explicitly after detaching the links to prevent memory leaks.

[shqnz]

This is the best explanation I have ever seen on deleting a node from BST.... To those who are still confused... I recommend them watching it again with full concentration rather than jumping to other videos..
Thanks @takeUforward😉

[rohan]

Thanks striver for this Tree series & all of your other series, I wish that people like you should born again & again in every verse so if you can educate creature of that planet very well for at least one domain. Once again thanks to you & god bless you, live long & god will fullfill you with prosperity.

[iamparitosh]

Completed all the 45 problems, thanks for the mashup striver.
Didn't watch the video lectures but excellent problem choice for intermediate candidates

[raghav]

Striver code works well, here is an alternative code that also makes sure that the tree isn't left, right weighted.
In my approach, we deal it in 2 Cases:

1. Case 1: Node with Two Children
If the node to be deleted has two children, we find the largest value in its left subtree (the rightmost node in the left subtree), replace the value of the node to be deleted with this largest value, and then recursively delete the duplicate node in the left subtree. This approach maintains the BST property and avoids skewing the tree.

2. Case 2: Node with One or No Child
If the node has only one child or no children, we directly replace the node with its child (or `nullptr` if no child exists). This handles both single-child and leaf node cases efficiently while preserving the BST structure.



class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode* ptr = root;
if(root == NULL) return root;
if(root->val < key){
root->right = deleteNode(root->right, key);
}
else if (root->val > key){
root-> left = deleteNode(root->left, key);
}
else{
if(root->left == NULL){
ptr = root;
root = root->right;
delete ptr;
}
else if(root->right == NULL){
ptr = root;
root = root->left;
delete ptr;
}
else{
ptr = root->left;
while(ptr->right != NULL){
ptr = ptr->right;
}
root->val = ptr->val;
root -> left = deleteNode(root->left, ptr->val);
}
}
return root;
}
};

[takeUforward]

Please likeeee, shareeee and :) Also follow me at Insta: Striver_79

[vineelpynam]

Simple Code using same approach:

TreeNode* deleteNode(TreeNode* root, int key) {
if( !root ) return NULL;
if( root->val < key ) root->right = deleteNode(root->right, key);
else if( root->val > key ) root->left = deleteNode(root->left, key);
else{
if( !root->right && !root->left ) return NULL;
else if( !root->right ) return root->left;
else if( !root->left ) return root->right;
else{
TreeNode* temp = root->right;
while( temp->left ) temp = temp->left;
temp->left = root->left;
return root->right;
}
}
return root;

}

🙂

[liftingMohit]

Bhaiya watched all 45 videos of Tree Series and I learnt a lot from them ... waiting for rest of the videos.. Thank You so much bhaiyaa

[NidhiKumari-vuoj]

watched the last explanation bit 3 times and did dry run. Thanks Striver

[Kpriyasing]

Completed upto here!
And it's really worth watching ✨

[amanshah]

I really appreciate your videos and intuitions!!!
Another approach :-
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root)return NULL;
NULL;
if(root->val==key)return helper(root);
TreeNode*par=root, *curr=root;
while(root){
if(root->val==key){
if(root->left){
auto rMostOfLeft=root->left;
while(rMostOfLeft->right){

}


else par->right=root->left;
}
else{

else par->right=root->right;
}
break;
}

else {par=root;root=root->left;}
}
return curr;
}
TreeNode* helper(TreeNode*root){
if(!root->left)return root->right;
if(!root->right)return root->left;
auto temp=root->left;

temp->right=root->right;
return root->left;
}

[Malayalam_learner]

Something to share !!

At start I mean before a month:
I used to be like striver teaching is not good he tells the concepts enthusiasticly but it's not worth my time.

But from last week as I saw videos again and again. Everything is so smooth and easy

I judged striver 🤡

But I felt the familiarity (through repetition)is whats makes dsa easy don't skip these gems !!!!

[saurabhmishra]

For java people, I would suggest going for the recursive way...it's much easier to understand. Here is the code -
public TreeNode deleteNode(TreeNode root, int key) {
//if null i.e. empty tree, return null

if(root == null){
return null;
}

//keep moving left/right until you don't find the key

if(key < root.val){
root.left = deleteNode(root.left, key);
}else if(key > root.val){
root.right = deleteNode(root.right, key);
}else{
//if key is found, check if it's left/right is empty

if(root.left == null){
return root.right;
}else if(root.right == null){
return root.left;
}
//otherwise find min in right subtree, replace with cureent value and delete that min node in right subtree
TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, root.val);
}
return root;
}

private TreeNode findMin(TreeNode node){
while(node.left != null){
node = node.left;
}
return node;
}

[lifegood]

Completed all these videos with notes as well, Please upload more you said you will upload 7-8 videos on weekend. Please do it if possible.

[karantaori]

I did the question on my own! Thanks to you Striver😄

[jayatanwani]

Your content is worth watching striver, thank you for everything you do!

[_-]

Hi Raj, great content and epic series, could you kindly let us know if there are more videos coming for Binary search tree concepts?

[ryanaugustine]

This is a bad stategy because the more you delete the more you make the tree unbalanced. In a balanced tree the time complexity for search is O(LogN) and in the most unbalanced tree (only left or right nodes) the time complexity is O(N).

[ranjeetkumbhar]

@striver, ❗❗❗❗BST does not allow duplicate values, so why are there two 8s in the example