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.
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😉
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; } };
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; }
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 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)
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).
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.
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).
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?
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
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
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.
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
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;
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 .....
#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
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
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]
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
amazing brother
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
Its just Crystal clear and amazing !
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.
Remember to take delete the node explicitly after detaching the links to prevent memory leaks.
Yes
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😉
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;
}
}
Completed all the 45 problems, thanks for the mashup striver.
Didn't watch the video lectures but excellent problem choice for intermediate candidates
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;
}
};
Completed upto here!
And it's really worth watching ✨
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
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;
}
Your content is worth watching striver, thank you for everything you do!
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;
}
🙂
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;
a not so simple solution >> hard to read soln
Hi Raj, great content and epic series, could you kindly let us know if there are more videos coming for Binary search tree concepts?
You have so much of money to waste, like wth joins a channel for a comment icon
@@abhiprojectz2995 thanks I dint notice I was continuing membership. I just stopped it. It seems there are no more meet ups.
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;
}
Striver is a cpp guy 9:34
Thank you bhaiya 😊😊 Aapsey google may milu gaa😎😎😎
What a crsip explanation.. Loved it
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.
meko kewal aapka hi samajh aata h aur koi ka kuch samajh ni padta thank you
great explaination and code, thanks raj bhaiya❤️
Wow as always, love your intuition and explanation
College?
I love you too
@@dipeshsaili4468 🤣🤣
@@prathameshkodgire8642 I love her bro
@@dipeshsaili4468 oh ok . May God bless both of you. Have a happy married life .
Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.
Great Job, thanks all your efforts !!
Loved your intuition !
Beautiful explanation
waiting for next 8 videos, thanks man!
Great content bhaiya 🙌
Amazing !!!! Explanation
bro this is so gold, thank you so much!
nice video thank you for such informative video
Finally understood the concept,
Thanks bhaiya ✨
thanks bro..completed the series..thank you!!
Amazing bro , thanks
All videos out?? Or is there any video yet to be uploaded?
Btw great work..🔥🔥
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thank you so much man! God Bless you!
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;
}
basically u are saying to find kind of inorder successor am I right?
@@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)
@@vaibhavpandey9779 it can either be inorder predecessor or successor, doesn't really matter.
@striver, ❗❗❗❗BST does not allow duplicate values, so why are there two 8s in the example
Amazing content!
The boys'
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).
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.
How bro do you have a code ? @@pulkitjain5159
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).
Don't remember asking
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;
}
};
```
Thank you
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?
totally depends, whatever is easy for you to understand
nice video
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
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
No bro, we have to consider all three cases: 0 child, 1 child and 2 children
@@shayaanrk yes thats kind of simpler than this
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.
No I checked the recursive one. It becomes too confusing
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;
}
@@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;
}
}
@@suryakiran2970 It isn't covering all the edge cases
i love you striver🤟
Great Video Thankyou so much.
very well explained
BST does not allow duplicate values, so why are there two 8s in the example
Bhaiya you are genius 🎉
It will go wrong if 14:21 3's right is suppose 9 how will you add 7 node to the right of it
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
Pepcoding solution is pretty clean n easy
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;
}
nice explanation
Great Work!
Next set of videos?
Clean Explanation.
major parts implemented by myself.
Thank you sir
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 .....
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;
}
}
UNDERSTOOD, AFTER 2 DAYS
why did it take so long for you
awesome explanation
Understood!!
thank u bhaiya :)
understood
#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
Same doubt
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
Thank striver!!!
Doesn't this fail for test case [5,3,6,2,4,null,7] and key = 5?
I had also add these to code: if(root.val == key) {
return helper(root);
}
and you didnt explain for leaf node, single child etc , missed the important part
Giving error while using tha same code to submit
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;
}
This approach increases the height of the tree which is not commendable
Below is my solution.... easy to understand.
public static Node deleteNode(Node node, int key) {
if(node == null) return null;
if(key == node.value) {
Node temp = node.left;
if(temp == null) return node.right;
while (temp.right != null) temp = temp.right;
temp.right = node.right;
return node.left;
}
if(key < node.value) node.left = deleteNode(node.left, key);
else node.right = deleteNode(node.right, key);
return node;
}
How about swapping the node until it becomes a leaf and then delete ? This takes 0(h) only rt
no bro , isi example mein swapping karke dekhlo , and just delete root node 8 , you will find things.
/**
* 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);
}
};
Gazab ka tree series
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
Very nice explanation as well as the code.
Good explaination
How is returning dummy gives the correct answer, it was as it is, there were no operations performed on that.
bhaiya, baaki ke bhi videos upload krdo, complete krke agle topic pe badna hai..
Please
Java wale be like: Mein kya karu fir job chod du😂🤣
#striver rock
understood great video
striver how many video are still to come in this playlist
It becomes frustrating to solve this if asked in an interview.
Why ??
Thanks a lot striver
Thank You!
Great Video
Epic as always, strive!
How can a bst have same node values ? 8 & 8 again
Bhaiya, when more videos will come ?
what if the given key is the root only?
While writing inorder traversal post deletion i found 8 is repeated
UNDERSTOOD
thankyou bhaiya
understood
good
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]
Bhaiya diagonal traversal of binary tree bhi add krdo isme
Tq sir