Delete Node in a BST - Leetcode 450 - Python

Solving Leetcode 450 - Delete Node in a BST.

0:00 - Read the problem
0:50 - Drawing Explanation
8:53 - Coding Explanation

leetcode 450

#neetcode #leetcode #python

[ericgithinji]

RIP to whoever gets this question in an interview without having studied the approach before

[VEDANSHSHARMA-ok]

Line 27 is so so clever
root.right = self.deleteNode(root.right, root.val)

[aadil]

That is the best Recursion I have ever seen so far!! Thank you NeedCode!!

[jessicachen]

I finally understand the solution after watching your video! You're amazing!

[MP-nyep]

Great explanation as always. Thank you

[StellasAdi]

That was bit tricky. In step 2 was thinking to append deleted nodes left chain to deleted nodes right nodes leftmost node.

[jakjun]

can u provides a tree example where time complexity is o(2h)?

[comingforyou]

can anyone explain me why we need to assign calls to root.right and root.left

[Rajib]

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

[tgixtdr]

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

[shivamtripathi]

This code have issue, when we have to delete root node.

[abhishekupadhyay]

Could you please explain how to do it Iteratively?

[andrewtitus]

I didnt think this one was that bad, but i have been practicing trees a bunch

[nithinsastrytellapuri]

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 ?

[alivepenmods]

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.

[ahmedmansour]

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

[khaledkord]

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

[jakjun]

and could u solves
memory leakage issue? the memory address of the left most found node still not delete yet.

[millrgj]

You need to account for an instance where the root is not actually equal to k, line 16 should check if k == root.val

[ashwanikumar]

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