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

[@takeUforward]

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

[@codeguy21]

amazing brother

[@namanlakhwani4752]

At least let us know till when the rest of the videos will be uploaded? So that we can plan accordingly. I'm waiting from last 2 weeks

[@h108pranavshinde3]

Its just Crystal clear and amazing !

[@NoBakwas]

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

[@imPriyansh77]

Yes

[@rohan8758]

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.

[@vineelpynam6547]

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

[@AmanKumar-xb7cw]

Replace this 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; } with TreeNode*temp=root->right; if(temp){ while( temp->left ) temp = temp->left; temp->left=root->left; return root->right; } return root->left;

[@Mel-up7un]

a not so simple solution >> hard to read soln

[@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😉

[@KS0607]

but its very confusing...not the best method i can say.. public class Solution { public TreeNode solve(TreeNode A, int B) { return deleteNode(A,B); } private TreeNode deleteNode(TreeNode A, int B){ if(A == null){ return null; } if(B < A.val){ A.left = deleteNode(A.left,B); } else if(B > A.val){ A.right= deleteNode(A.right,B); } else{ if(A.left == null && A.right == null){ return null; } else if(A.right == null){ return A.left; } else if(A.left == null){ return A.right; } else{ TreeNode temp = findMaxfromLeft(A.left); A.val = temp.val; A.left = deleteNode(A.left, temp.val); } } return A; } private TreeNode findMaxfromLeft(TreeNode A){ while(A.right != null){ A = A.right; } return A; } }

[@iamparitosh]

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

[@saurabhmishra1587]

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

[@Kpriyasing]

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

[@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

[@amanshah1650]

I really appreciate your videos and intuitions!!! Another approach :- TreeNode* deleteNode(TreeNode* root, int key) { if(!root)return NULL; if(!root->left&&!root->right&&root->val==key)return 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){ rMostOfLeft=rMostOfLeft->right; } rMostOfLeft->right=root->right; if(par->val>root->val)par->left=root->left; else par->right=root->left; } else{ if(par->val>root->val)par->left=root->right; else par->right=root->right; } break; } if(key>root->val){par=root;root=root->right;} 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; while(temp->right)temp=temp->right; temp->right=root->right; return root->left; }

[@jayatanwani5979]

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

[@lifegood6401]

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.

[@dingo_5998]

Thank you bhaiya 😊😊 Aapsey google may milu gaa😎😎😎

[@_-6912]

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

[@abhiprojectz2995]

You have so much of money to waste, like wth joins a channel for a comment icon

[@_-6912]

@@abhiprojectz2995 thanks I dint notice I was continuing membership. I just stopped it. It seems there are no more meet ups.

[@harrypottah9862]

Striver is a cpp guy 9:34

[@shivangisrivastava1158]

Wow as always, love your intuition and explanation

[@dipeshsaili4468]

College?

[@leetcoder1159]

I love you too

[@prathameshkodgire8642]

@@dipeshsaili4468 🤣🤣

[@dipeshsaili4468]

@@prathameshkodgire8642 I love her bro

[@prathameshkodgire8642]

@@dipeshsaili4468 oh ok . May God bless both of you. Have a happy married life .

[@aniketkhede6894]

meko kewal aapka hi samajh aata h aur koi ka kuch samajh ni padta thank you

[@arjunsolanki752]

great explaination and code, thanks raj bhaiya❤️

[@vaibhavpandey9779]

Instead doing this, we can find the minimum value in the right subtree or maximum value in the left subtree, copy its value in the node to be deleted and delete the minimum/maximum node. Here's the code: Node* Delete(Node* r, int value){ if (r==NULL) return r; else if (valuedata) r->left = Delete(r->left,value); else if (value>r->data) r->right = Delete(r->right,value); else{ if (r->left == NULL && r->right == NULL){ delete r; r=NULL; //as it will be dangling } else if (r->left == NULL) { Node* temp = r; r = r->right; delete temp; } else if (r->right == NULL) { Node* temp = r; r = r->left; delete temp; } else { Node* temp = MinBstNode(r->right); r->data = temp->data; r->right = Delete(r->right,temp->data); } } return r; }

[@blackstargaming3678]

basically u are saying to find kind of inorder successor am I right?

[@vaibhavpandey9779]

@@blackstargaming3678 No, the inorder successor in BST would be the next largest node as inorder of BST is sorted. I am talking about the maximum node in the left subtree (because we have to maintain the BST property)

[@rajjagtap7737]

@@vaibhavpandey9779 it can either be inorder predecessor or successor, doesn't really matter.

[@ipawanbhatt]

What a crsip explanation.. Loved it

[@paragroy5359]

Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.

[@108_adityakumar6]

Great content bhaiya 🙌

[@shilpadam6415]

Great Job, thanks all your efforts !!

[@anandtripathi]

waiting for next 8 videos, thanks man!

[@ombhandari6148]

Finally understood the concept, Thanks bhaiya ✨

[@ryanaugustine5940]

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).

[@pulkitjain5159]

ya but intution wise it is great , another approach what we can do is just swap the greater numbers with the node until your node becomes leaf node , and at last delete this node.

[@KaifKhan-sb2yr]

How bro do you have a code ? ​@@pulkitjain5159

[@kishoregowda8210]

The question is asking us to just delete the node, so this approach is more than enough. If you want to maintain the log(N) time complexity, then you have to go with something like self balancing tree (AVL).

[@WowSirSmallFan]

Don't remember asking

[@Kpriyasing]

Amazing content!

[@saurabhsagar3134]

The boys'

[@JohnWick-kh7ow]

I think the recursive solution would be short and better. Btw, I watched all videos of this playlist. Your videos are awesome as always. Please upload the remaining videos.

[@pratyushnarain5220]

No I checked the recursive one. It becomes too confusing

[@suryakiran2970]

Recursive solution Node* insertNode(Node* root, int newKey) { if(root == NULL) return new Node(newKey); if(newKey < root->data) root->left = insertNode(root->left, newKey); else root->right = insertNode(root->right, newKey); return root; }

[@KS0607]

@@pratyushnarain5220 public class Solution { public TreeNode solve(TreeNode A, int B) { return deleteNode(A,B); } private TreeNode deleteNode(TreeNode A, int B){ if(A == null){ return null; } if(B < A.val){ A.left = deleteNode(A.left,B); } else if(B > A.val){ A.right= deleteNode(A.right,B); } else{ if(A.left == null && A.right == null){ return null; } else if(A.right == null){ return A.left; } else if(A.left == null){ return A.right; } else{ TreeNode temp = findMaxfromLeft(A.left); A.val = temp.val; A.left = deleteNode(A.left, temp.val); } } return A; } private TreeNode findMaxfromLeft(TreeNode A){ while(A.right != null){ A = A.right; } return A; } }

[@avanishrivastava4570]

@@suryakiran2970 It isn't covering all the edge cases

[@gouravkushwaha68]

Beautiful explanation

[@temp1-f3u]

nice video thank you for such informative video

[@mixshots1801]

I did like this using C++ using the second approach ``` /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root==NULL)return NULL; if(root->val==key){ if(root->right){ auto f = root->right; while(f->left!=NULL){ f=f->left; } f->left=root->left; root->left=root->right; } return root->left; } else if(root->val>key) root->left=deleteNode(root->left,key); else root->right= deleteNode(root->right,key); return root; } }; ```

[@VivekKumar-zo7kr]

All videos out?? Or is there any video yet to be uploaded? Btw great work..🔥🔥

[@ArdentMusicLover]

Loved your intuition !

[@solankiketul5640]

I can think of another solution as well. We can replace the node to be deleted with the leaf node with the greatest value on the left subtree or the leaf node with the smallest value on the right subtree. Like in our example, replacing 5 with 4 and keeping the tree as it is. It will maintain the height difference of the tree

[@AmanjotSingh-rj7ox]

but what if the smallest or greatest values you are talking about are not leaf nodes and they have a child with them, they you might loose their childs. try with this example : [8,3,6,2,null,null,7] try deleting 8

[@shayaanrk]

No bro, we have to consider all three cases: 0 child, 1 child and 2 children

[@deveshdubey6776]

thanks bro..completed the series..thank you!!

[@Ragehunter]

bro this is so gold, thank you so much!

[@piyushacharya7696]

#HELP Could someone explain that if we want to remove the root node then how the code is working? like how the left part and right part is joining together. Eg: 10:19

[@nikharbehera4038]

Same doubt

[@anshumaan1024]

as per striver's code : 8->right = 9->right, and node 9 will be removed so, tree will be [8,5,12,3,7,10,13,null,null,null,null,null,11], which is will be a BST

[@prasadm3614]

Pepcoding solution is pretty clean n easy

[@deepakantoj432]

the question is to delete a node from BST my approach is that i'll first get the key node and then also get the parent node of the key node . connect the parent node's left or right to key node's right . and store the key node's left in a temp node i'll traverse to the very left of the newly connected parent's left and attach the temp . /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { TreeNode node = solve(root,key); // key node TreeNode n = helper(root,key); // parent node if(n.left != null) if( n.left.val == key) n.left = node.right; else if(n.right != null) if(n.right.val == key) n.right = node.right; TreeNode left = node.left; TreeNode cur = node.right; while(cur.left!=null) { cur = cur.left; } cur.left = left; return root; } public TreeNode helper(TreeNode root , int val) { if(root == null) return null; if(root.left!=null) { if(val == root.left.val) return root; } else if(root.right!=null){ if(val == root.right.val) return root; } return val > root.val ? helper(root.right , val) : helper(root.left , val); } public TreeNode solve(TreeNode root , int val) { if(root == null) return null; if(val == root.val) return root; return val > root.val ? solve(root.right , val) : solve(root.left , val); } } where have i gone wrong anybody please help

[@stith_pragya]

Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@arif2921]

Amazing !!!! Explanation

[@abirpaul9027]

Hey striver this is my viewed video of your channel.I have a doubt everywhere they are saying to bring the inorder predecessor or successor to delete a non leaf node and you are giving this approach which one should we go for?

[@FusionArcs]

totally depends, whatever is easy for you to understand

[@kedarsatwik6938]

Much an easy way to memorize the intution TNode* delMergeBST(TNode* root){ // root is to be removed, so we will merge all leftSubTree to right subTree and return a node // returned node will act like subsitute for del Node if (root->left == NULL){ return root->right; } if (root->right == NULL){ return root->left; } // if both right, left not null // all left subtree nodes are lesser than all right subtree nodes TNode* leftSubTree = root->left; TNode* rightSubTree = root->right; TNode* temp = rightSubTree; // now move temp so that temp->left is null , so we can attach leftSubTree to it while (temp->left != NULL){ temp = temp->left; } temp->left = leftSubTree; return rightSubTree; } TNode* del_prevNodeBST(TNode* root,int x){ if (root == NULL) return NULL; TNode* temp = root; while (temp->left != NULL || temp->right != NULL){ if (temp->left != NULL){ if (temp->left->data == x){ return temp; } } if (temp->right != NULL){ if (temp->right->data == x){ return temp; } } if (temp->data < x){ temp = temp->right; }else if (temp->data > x){ temp = temp->left; } if (temp == NULL){ return NULL; } } return NULL; } TNode* deleteNodeBST(TNode* root, int x) { if (root == NULL) return NULL; if (root->data == x){ return delMergeBST(root); } TNode* prevNode = del_prevNodeBST(root,x); if (prevNode == NULL) return root; if (prevNode->left != NULL && prevNode->left->data == x){ prevNode->left = delMergeBST(prevNode->left); return root; } if (prevNode->right != NULL && prevNode->right->data == x){ prevNode->right = delMergeBST(prevNode->right); return root; } return root; }

[@ranjeetkumbhar]

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

[@ayushnath3768]

This approach increases the height of the tree which is not commendable

[@jr_jeet]

Bhaiya you are genius 🎉

[@rishabhgoyal8110]

Thank you so much man! God Bless you!

[@manaskhare412]

UNDERSTOOD, AFTER 2 DAYS

[@utkarsh_108]

why did it take so long for you

[@codding32world50]

It will go wrong if 14:21 3's right is suppose 9 how will you add 7 node to the right of it

[@ritikshandilya7075]

Amazing bro , thanks

[@kekoHere0610]

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

[@Weirdvloggertrue]

Great Work! Next set of videos?

[@harshadevarakonda7965]

It would be better understood if you had explained about inorder predecessor and inorder successor because eventually we are replacing the node to be deleted with either of the two .....

[@KS0607]

public class Solution { public TreeNode solve(TreeNode A, int B) { return deleteNode(A,B); } private TreeNode deleteNode(TreeNode A, int B){ if(A == null){ return null; } if(B < A.val){ A.left = deleteNode(A.left,B); } else if(B > A.val){ A.right= deleteNode(A.right,B); } else{ if(A.left == null && A.right == null){ return null; } else if(A.right == null){ return A.left; } else if(A.left == null){ return A.right; } else{ TreeNode temp = findMaxfromLeft(A.left); A.val = temp.val; A.left = deleteNode(A.left, temp.val); } } return A; } private TreeNode findMaxfromLeft(TreeNode A){ while(A.right != null){ A = A.right; } return A; } }

[@divyakarlapudi]

Great Video Thankyou so much.

[@vishaljaiswar6441]

i love you striver🤟

[@aryansinha1818]

Thank you

[@prathameshkodgire8642]

Java wale be like: Mein kya karu fir job chod du😂🤣

[@sarthakbhatia7888]

class Solution { public: TreeNode* deleteNode(TreeNode* root, int k) { if (!root) { return root; } if (root->val == k) { TreeNode* temp = root->right; while(temp && temp->left) { temp = temp->left; } if (temp) { temp->left = root->left; return root->right; } else { return root->left; } } else if (root->val > k) { root->left = deleteNode(root->left, k); } else { root->right = deleteNode(root->right, k); } return root; }

[@RamKumar-kz8gg]

bhaiya, baaki ke bhi videos upload krdo, complete krke agle topic pe badna hai.. Please

[@smeetkothari5160]

Doesn't this fail for test case [5,3,6,2,4,null,7] and key = 5?

[@smeetkothari5160]

I had also add these to code: if(root.val == key) { return helper(root); }

[@mohammedzaidkhan5687]

nice video

[@Parth.Deshpande]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root==NULL){ return NULL; } if(root->val == key){ return helper(root); } TreeNode* dummy = root; while(root!=NULL){ if(root->val>key){ // it's on left side if(root->left!=NULL && root->left->val==key){ root->left = helper(root->left); break; }else{ root=root->left; } }else{ //it's on right if(root->right!=NULL && root->right->val==key){ root->right=helper(root->right); break; }else{ root=root->right; } } } return dummy; } TreeNode* helper(TreeNode* root){ if(root->left==NULL){ return root->right; } if(root->right==NULL){ return root->left; } TreeNode* rightside = root->right; TreeNode* lastright = findlastright(root->left); lastright->right = rightside; return root->left; } TreeNode* findlastright(TreeNode* root){ if(root->right==NULL){ return root; } return findlastright(root->right); } };

[@vishaljain4642]

Gazab ka tree series

[@abhaythakur2597]

very well explained

[@wonderfulquotes6484]

awesome explanation

[@iWontFakeIt]

I solved this dividing into two parts Part 1: writing a function that can delete the root node of a bst and return new root node, Part 2: writing a function to search for a given key in bst and then use the function written in part 1 to make reconnections. I hope this helps a lot while solving this type of problems. class Solution { public: TreeNode* makeReconnections(TreeNode* root){ if(root->left==NULL) return root->right; if(root->right==NULL) return root->left; TreeNode* rootRightChild = root->right; TreeNode* rootLeftChild = root->left; TreeNode* temp = rootLeftChild; while(temp->right) temp = temp->right; temp->right = rootRightChild; return rootLeftChild; } TreeNode* solve(TreeNode* root, int key){ // base case if(!root) return NULL; if(root->val == key){ // delete it return makeReconnections(root); }else if(root->val > key){ root->left = solve(root->left, key); return root; }else{ root->right = solve(root->right, key); return root; } } TreeNode* deleteNode(TreeNode* root, int key) { if(!root) return NULL; // search for the node and then delete return solve(root, key); } }; Here deleteNode() is the function which calls the helpers solve() [part 2 function] which in turn uses the function makeReconnections() [part 1 function]

[@UECAshutoshKumar]

Thank you sir

[@prasadm3614]

How about swapping the node until it becomes a leaf and then delete ? This takes 0(h) only rt

[@pulkitjain5159]

no bro , isi example mein swapping karke dekhlo , and just delete root node 8 , you will find things.

[@PrinceKumar-el7ob]

thank u bhaiya :)

[@amanbhadani8840]

Very nice explanation as well as the code.

[@Hrit]

Clean Explanation.

[@BinaryNerd]

nice explanation

[@shreyashachoudhary480]

Epic as always, strive!

[@rohandevaki4349]

and you didnt explain for leaf node, single child etc , missed the important part

[@jiteshjoshisde3154]

Giving error while using tha same code to submit

[@ParichayPlate_Tak]

striver how many video are still to come in this playlist

[@SubhamYadav-q1r]

How is returning dummy gives the correct answer, it was as it is, there were no operations performed on that.

[@bindumahapatra8234]

if a node asked to delete which is not present in tree, to address it inside while we can write if else-if else to break and return -1

[@shivamehta6537]

Great explanation!!

[@devbhattacharya153]

Thanks a lot striver

[@kishoregowda8210]

Below is my solution.... easy to understand. public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return root; if(root.val == key){ if(root.right != null && root.left != null) root.right = insertNode(root.right, root.left); return root.right == null ? root.left : root.right; } if(key > root.val) root.right = deleteNode(root.right, key); else root.left = deleteNode(root.left, key); return root; } public TreeNode insertNode(TreeNode root, TreeNode node) { if(root == null) return node; if(node.val > root.val) root.right = insertNode(root.right, node); else root.left = insertNode(root.left, node); return root; }

[@nishantingle1438]

It becomes frustrating to solve this if asked in an interview.

[@nikharbehera4038]

Why ??

[@anshulgoel1940]

Same approach but more concise solution (in Kotlin) fun deleteNodeBST(head: Node?, target: Int): Node? { if(head == null) return null if(head!!.`val` == target){ val left = head!!.left val right = head!!.right if(left != null) { findGreatest(left)!!.right = right return left } return right } if(target < head!!.`val`){ head!!.left = deleteNodeBST(head!!.left, target) } else{ head!!.right = deleteNodeBST(head!!.right, target) } return head } fun findGreatest(node: Node?): Node? { if(node == null) return null var temp = node while(temp!!.right != null){ temp = temp!!.right } return temp }

[@unfixflip5332]

Bhaiya diagonal traversal of binary tree bhi add krdo isme

[@PratibhaSharma-h7b]

While writing inorder traversal post deletion i found 8 is repeated

[@onlysparsh]

How can a bst have same node values ? 8 & 8 again

[@asifbasheerkhan2855]

Bhaiya, when more videos will come ?

[@harshitjaiswal9439]

understood

[@harshitsamdhani2426]

understood great video

[@divyaagarwal3091]

Understood!!

[@sans.creates]

Thank You!

[@adebisisheriff159]

Thank striver!!!

[@amarjeetkumarsingh733]

Great Video

[@AmanSharma-pb8hi]

what if the given key is the root only?

[@prithvigupta8215]

9:23

[@skye7109]

Justice for Java people xD

[@Rieshu-l9i]

#striver rock

[@nishantgarg2815]

GFG solution was a bit easier

[@SachinSingh-id8mf]

thankyou bhaiya

[@venutalla5932]

Tq sir

[@utkarsh_108]

is it giving TLE for anyone else too ?

[@jiteshjoshisde3154]

My solution is not accepting in leetcode