It's a standard data structure (binary tree) method. If you've ever taken Data Structures and Algorithms then you've seen this exact thing. It's basically like not knowing for-while loops or a (a slightly lengthier) print statement, except for DSA. Not trying to be an elitist but hopefully if anyone is self taught and doesn't know DSA they can take the time to learn it so they don't get tripped up by what is practically a leetcode easy. Btw I recommend neetcode's DSA course which I'm currently taking. He's basically the GOAT for this in 2024 (and probably will remain so in 2025 and 2026 at least)
@@doc9448What point are you trying to make? By watching this video, everyone here is already studying DSA. Sometimes the basic primitives we use to approach algorithms problems require a unique approach. Coming to this solution in a 30-45min interview, while trying to fulfill the criteria of the interview (voicing your thoughts, asking clarifying questions, making sense to the interviewer) is not a trivial thing to do.
Here I thought I got this correct after all the example cases got passed and all I needed to solve was [0]; expected [] . if(prev != null && prev.next != null){ prev.left = root.right; pref.left.left = root.left; }
I'm a bit confused. Technically don't you think we are not deleting it? We are swapping values and deleting a different node. Also, what if the data is huge in the nodes? It in itself can take additional time. Found these questions in leetcode comment section of similar approach answers.
I'd reject anyone that changes node values. Pointer from up the call stack could be maintaining reference to any node, satellite data could also be involved. CLRS has a brilliant explanation on how to delete a node in a BST.
Hey hi myself rakesh, I have found a mistake in ur explanation at 8:17 time that u will replace 5 value in node 4 but u only search for min in right subtree if node 4 has both right and left, but here 4 does not have left so we return node 4 right instead of searching for min in right subtree
why is the time complexity the height of tree i.e. O(log(n)) instead of O(n) ? what if the tree is skewed and we have to delete the left most or right most element? then in that case we have to traverse all the elements right ?
The time complexity is O(h) where h is the height of the tree. For balanced BSTs, the height is logn, so the complexity in that case is O(logn). For scewed BSTs, the worst-case height is n, so the time complexity in that case is O(n).
What if the smallest value in the right side tree was smaller than the current left. for example the node 4 had a left side 1. 50 / \ 30 60 / \ \ 2 40 70 / 1 will be converted to this INVALID bst: 50 / \ 1 60 / \ \ 2 40 70
its doable. Just solve linked list node removal question. Than draw BST with height 1, 2, 3, 4 and take a look how is efficient to remove nodes with different values. You will be able to solve this after some practice. Its not about solution of this particular problem but to learn methods how to research problems in general. How to dig =)
Can someone explain the assignment part at 10:08? Are we storing the root.left and root.right variables in order to later check if the node we found has a left or right child (as seen in the else statement later below)?
If you mean root.left and root.right on lines 12-15, we are not storing variables here, we are calling deleteNode recursevely and assigning it's result to left or right node. We call deleteNode recursively and trying to find "key". From line 12 to line 15, we comparing key to current node value, if search key is bigger than val we go right, if search key is less then val we go left. Because in valid Binary Search Tree left node has a value less than or equal to its parent, the right one has a val greater or equal to parent node. From line 16 to line 20 we are checking for case when found key node that has 0 or 1 child. Starting from line 22 we know that "key" node has 2 child nodes. So from line 23 to 26 we are searching for "min value" on right side of found "key" node, and replace "key" with that "min value". Now we need to delete min-val. Because we copied it's value to "key" node. So at line 27 we call deleteNode recursively on right side of found "key" node and pass root.val (which is equal to min val) as "new search key". How it removes "min value"? At the end it reaches to base case where root is null (line 9) or it will reach case with 0 and 1 child (lines 17-20).
We are using recursion. So after we remove a left child, we have to connect (point) it to the replaced value which can be None or some other element. In the example above, after deleting 3, we have to replace it with 4. So after putting 4 there, we have to connect the left of 5 to point to that 3. That's what is happening. You can do this on a paper by drawing yourself to understand it better 😬🫡
java script solution with more comments: // T: O(log(n)), S: O(1) (not counting stack frames for recursion) // being n the amount of nodes in the tree // T: O(h), S: O(h) (counting h stack frames for recursion) // being h the height of the tree (max elements of the bst = n = 2^h) if (null === root) { return null; } if (root.val === key) { // to delete a leaf node (no children) we can just return null if (null === root.left && null === root.right) { return null; } // at this point we need to delete the current node. so, we need to return a different one // we need to pick either the left or the right node if (null !== root.left && null !== root.right) { // this a complicated edge case that we can't solve right away // // we could pick the root.left node, but what if (root.left.right !== null)? where // are we going to attach our root.right subtree without overwriting any existing // reference? // // also, we could pick the root.right node, but what if (root.right.left !== null) too? // // so, these are our two possible (and equivalent) options: // 1) pick our root.right node as the root node, and find the minimum node in // the right subtree that has no left pointer, and assign the root.left node to it. // // 2) pick our root.left node as the root node, and find the maximum node in // the left subtree that has no right pointer, and assign the root.right node to it. // // here's an example of deleting node with val=5 without breaking the BST choosing option (1) // // 5 8 // / \ / \ // 3* 8 7 9 // / \ / \ ---> / // 2 4 7 9 6 // / / // 6 3* // / \ // 2 4 // // we'll choose option (1) and we'll find the minimum number in the right subtree that // has no left pointer // that one is going to be the node that will link to the left subtree of the current // -soon to be deleted- node. by doing that we'll preserve the structure of the BST // (nodes to the left of a node should be smaller, and numbers to the // right should be greater). let curr = root.right; while (curr.left) { curr = curr.left; } curr.left = root.left; return root.right; }
// if left/right is null, then we can safely pick the one that is not null without // breaking the BST if (null === root.left) { return root.right; } if (null === root.right) { return root.left; } }
if (key < root.val) { // look for our target node in the left subtree root.left = deleteNode(root.left, key); } else { // look for our target node in the right subtree root.right = deleteNode(root.right, key); } return root; };
@@denysivanov3364 thanks. i've already solved some issues using linked lists and bst, including some medium difficulty ones, but this one looks specifically terrifying i'll just keep practicing, i guess. hopefully i'll learn something after all
@@alexanderp7521 I recommend reading a book how to solve it by George Polya. It will help to develop methods how to solve problems in general. Talking about this don't give up. Just draw BST with height 1, 2, 3, 4. Look at edge cases, draw how tree should change to maintain BST property, from where you need to move Node to keep tree nice etc. Just draw and take a look. I did it iterative. Do it little by little, don't give up. You will learn new things how to dig.
@@alexanderp7521 Just draw BST of size 1, 2, 3, 4 and look what you need to do there. How to find node, with what it needs to be replaced etc. Look for edge cases. I did it iteratively its doable.
RIP to whoever gets this question in an interview without having studied the approach before
It's a standard data structure (binary tree) method. If you've ever taken Data Structures and Algorithms then you've seen this exact thing. It's basically like not knowing for-while loops or a (a slightly lengthier) print statement, except for DSA. Not trying to be an elitist but hopefully if anyone is self taught and doesn't know DSA they can take the time to learn it so they don't get tripped up by what is practically a leetcode easy. Btw I recommend neetcode's DSA course which I'm currently taking. He's basically the GOAT for this in 2024 (and probably will remain so in 2025 and 2026 at least)
@@doc9448 not everyone is from CS background
@@doc9448 elitist
@@doc9448 I took a graduate level DSA course, no I did not see this exact thing lol.
@@doc9448What point are you trying to make? By watching this video, everyone here is already studying DSA. Sometimes the basic primitives we use to approach algorithms problems require a unique approach. Coming to this solution in a 30-45min interview, while trying to fulfill the criteria of the interview (voicing your thoughts, asking clarifying questions, making sense to the interviewer) is not a trivial thing to do.
That is the best Recursion I have ever seen so far!! Thank you NeedCode!!
I finally understand the solution after watching your video! You're amazing!
Line 27 is so so clever
root.right = self.deleteNode(root.right, root.val)
That was bit tricky. In step 2 was thinking to append deleted nodes left chain to deleted nodes right nodes leftmost node.
It's another approach that works also perfectly. Just a little bit more work to do
If you're looking for today's daily LC problem, you can find it here czcams.com/video/UbyhOgBN834/video.html
Here I thought I got this correct after all the example cases got passed and all I needed to solve was [0]; expected [] .
if(prev != null && prev.next != null){
prev.left = root.right;
pref.left.left = root.left;
}
Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I'm a bit confused. Technically don't you think we are not deleting it? We are swapping values and deleting a different node. Also, what if the data is huge in the nodes? It in itself can take additional time.
Found these questions in leetcode comment section of similar approach answers.
Great explanation as always. Thank you
Thank you sir for all your efforts😁
I'd reject anyone that changes node values.
Pointer from up the call stack could be maintaining reference to any node, satellite data could also be involved.
CLRS has a brilliant explanation on how to delete a node in a BST.
lol, no one likes you
so gooddddd thank you so much
Hey hi myself rakesh,
I have found a mistake in ur explanation at 8:17 time that u will replace 5 value in node 4 but u only search for min in right subtree if node 4 has both right and left, but here 4 does not have left so we return node 4 right instead of searching for min in right subtree
Thank you
I didnt think this one was that bad, but i have been practicing trees a bunch
can u provides a tree example where time complexity is o(2h)?
U a BST God
You need to account for an instance where the root is not actually equal to k, line 16 should check if k == root.val
Doesn't he account for root != k with root.val > k and root.val < k? Which other possibilities are there?
why is the time complexity the height of tree i.e. O(log(n)) instead of O(n) ? what if the tree is skewed and we have to delete the left most or right most element? then in that case we have to traverse all the elements right ?
If it's skewed then its not a BST
@@michaelrosa385Couldn't it still be a BST? If it was always balanced it would be an AVL.
The time complexity is O(h) where h is the height of the tree.
For balanced BSTs, the height is logn, so the complexity in that case is O(logn). For scewed BSTs, the worst-case height is n, so the time complexity in that case is O(n).
What if the smallest value in the right side tree was smaller than the current left. for example the node 4 had a left side 1.
50
/ \
30 60
/ \ \
2 40 70
/
1
will be converted to this INVALID bst:
50
/ \
1 60
/ \ \
2 40 70
That won't be a valid binary search tree case, 1 should be placed on the left child of 2 instead of 40
This code have issue, when we have to delete root node.
Could you please explain how to do it Iteratively?
its doable. Just solve linked list node removal question. Than draw BST with height 1, 2, 3, 4 and take a look how is efficient to remove nodes with different values. You will be able to solve this after some practice. Its not about solution of this particular problem but to learn methods how to research problems in general. How to dig =)
Can someone explain the assignment part at 10:08?
Are we storing the root.left and root.right variables in order to later check if the node we found has a left or right child (as seen in the else statement later below)?
If you mean root.left and root.right on lines 12-15, we are not storing variables here, we are calling deleteNode recursevely and assigning it's result to left or right node.
We call deleteNode recursively and trying to find "key". From line 12 to line 15, we comparing key to current node value, if search key is bigger than val we go right, if search key is less then val we go left. Because in valid Binary Search Tree left node has a value less than or equal to its parent, the right one has a val greater or equal to parent node.
From line 16 to line 20 we are checking for case when found key node that has 0 or 1 child.
Starting from line 22 we know that "key" node has 2 child nodes.
So from line 23 to 26 we are searching for "min value" on right side of found "key" node, and replace "key" with that "min value".
Now we need to delete min-val. Because we copied it's value to "key" node. So at line 27 we call deleteNode recursively on right side of found "key" node and pass root.val (which is equal to min val) as "new search key". How it removes "min value"? At the end it reaches to base case where root is null (line 9) or it will reach case with 0 and 1 child (lines 17-20).
@@gani3813 Thanks, great explanation
and could u solves
memory leakage issue? the memory address of the left most found node still not delete yet.
Python garbage collector handles this as it falls out of scope in the call stack
this shouldn't be medium fr
Too easy or too hard?
@@mk-19memelauncher65 too easy
@@mk-19memelauncher65 not too hard, but if you try to solve it iteratively (to save those recursion overheads) then it becomes a bit hard
can anyone explain me why we need to assign calls to root.right and root.left
We are using recursion. So after we remove a left child, we have to connect (point) it to the replaced value which can be None or some other element.
In the example above, after deleting 3, we have to replace it with 4. So after putting 4 there, we have to connect the left of 5 to point to that 3. That's what is happening.
You can do this on a paper by drawing yourself to understand it better 😬🫡
😵
java script solution with more comments:
// T: O(log(n)), S: O(1) (not counting stack frames for recursion)
// being n the amount of nodes in the tree
// T: O(h), S: O(h) (counting h stack frames for recursion)
// being h the height of the tree (max elements of the bst = n = 2^h)
if (null === root) { return null; }
if (root.val === key) {
// to delete a leaf node (no children) we can just return null
if (null === root.left && null === root.right) { return null; }
// at this point we need to delete the current node. so, we need to return a different one
// we need to pick either the left or the right node
if (null !== root.left && null !== root.right) {
// this a complicated edge case that we can't solve right away
//
// we could pick the root.left node, but what if (root.left.right !== null)? where
// are we going to attach our root.right subtree without overwriting any existing
// reference?
//
// also, we could pick the root.right node, but what if (root.right.left !== null) too?
//
// so, these are our two possible (and equivalent) options:
// 1) pick our root.right node as the root node, and find the minimum node in
// the right subtree that has no left pointer, and assign the root.left node to it.
//
// 2) pick our root.left node as the root node, and find the maximum node in
// the left subtree that has no right pointer, and assign the root.right node to it.
//
// here's an example of deleting node with val=5 without breaking the BST choosing option (1)
//
// 5 8
// / \ / \
// 3* 8 7 9
// / \ / \ ---> /
// 2 4 7 9 6
// / /
// 6 3*
// / \
// 2 4
//
// we'll choose option (1) and we'll find the minimum number in the right subtree that
// has no left pointer
// that one is going to be the node that will link to the left subtree of the current
// -soon to be deleted- node. by doing that we'll preserve the structure of the BST
// (nodes to the left of a node should be smaller, and numbers to the
// right should be greater).
let curr = root.right;
while (curr.left) { curr = curr.left; }
curr.left = root.left;
return root.right;
}
// if left/right is null, then we can safely pick the one that is not null without
// breaking the BST
if (null === root.left) { return root.right; }
if (null === root.right) { return root.left; }
}
if (key < root.val) {
// look for our target node in the left subtree
root.left = deleteNode(root.left, key);
} else {
// look for our target node in the right subtree
root.right = deleteNode(root.right, key);
}
return root;
};
there is no way i'm going to remember this code 💀
you need to draw BST and look at edge cases. You can solve this stuff on your own after some practice. Begin from linked lists.
@@denysivanov3364 thanks. i've already solved some issues using linked lists and bst, including some medium difficulty ones, but this one looks specifically terrifying
i'll just keep practicing, i guess. hopefully i'll learn something after all
@@alexanderp7521 I recommend reading a book how to solve it by George Polya. It will help to develop methods how to solve problems in general. Talking about this don't give up. Just draw BST with height 1, 2, 3, 4. Look at edge cases, draw how tree should change to maintain BST property, from where you need to move Node to keep tree nice etc. Just draw and take a look. I did it iterative. Do it little by little, don't give up. You will learn new things how to dig.
@@alexanderp7521 Just draw BST of size 1, 2, 3, 4 and look what you need to do there. How to find node, with what it needs to be replaced etc. Look for edge cases. I did it iteratively its doable.
Why is this so hard😢
Thank You