else if (root.left==null && root.right==null) //considering it to be a leaf node remove the node itself;
else // considering it to be internal node find the max in left subtree,replace with node and remove max at leaf. or find the min in right subtree,replace with node and remove min at leaf .
how do you know it's necessarily a leaf once you pass the (key > root) and (key < root) conditions? Doesn't this simply mean you've found the node that matches the key? I don't understand how you can imply that it's a leaf node just because key == root.
1. When present root matches key, it may be leaf or internal node.
2. If no left child, return right child as answer. This moves the appropriate pointer from previous root (parent of the present root which is under consideration) to right child of present root. Thus, present root is deleted.
3. Or, check if right child exists & apply same logic in point 2 above for left child.
4. Otherwise, it is an internal node and proceed to delete it accordingly.
5. Or, if the present root passed the first two conditions and doesn't have a left or right child, then it is a leaf node, and by Agilowen's algorithm, a null pointer is returned, thus effectively deleting the present root.
I will modify it slightly as below:
else if (root.left==null && root.right==null) //considering it to be a leaf node remove the node itself;
else // considering it to be internal node find the max in left subtree,replace with node and remove max at leaf. or find the min in right subtree,replace with node and remove min at leaf .
rahulsaurav189 1 month ago
HAVE YOU TESTED IT?I DONT THINK IT WILL WORK,
logic is when root.left is null, remove entire root.right(root.right itself can be a subtree) and deleting all will not solve the purpose.
rahulsaurav189 1 month ago
how do you know it's necessarily a leaf once you pass the (key > root) and (key < root) conditions? Doesn't this simply mean you've found the node that matches the key? I don't understand how you can imply that it's a leaf node just because key == root.
denebgarza 3 months ago
@denebgarza
The logic:
1. When present root matches key, it may be leaf or internal node.
2. If no left child, return right child as answer. This moves the appropriate pointer from previous root (parent of the present root which is under consideration) to right child of present root. Thus, present root is deleted.
3. Or, check if right child exists & apply same logic in point 2 above for left child.
4. Otherwise, it is an internal node and proceed to delete it accordingly.
DaveJLin 1 month ago
@denebgarza
I should also add:
5. Or, if the present root passed the first two conditions and doesn't have a left or right child, then it is a leaf node, and by Agilowen's algorithm, a null pointer is returned, thus effectively deleting the present root.
DaveJLin 1 month ago in playlist More videos from Agilowen
Hey, thanks a lot, your videos are awesome.
Writing an exam tomorrow, very good repetition. Though I think i wouldn't understand if I never heard of this topic.
dired1 7 months ago