1
$\begingroup$

Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion.

Case 1: The node is a leaf node. In that case you can simply delete the pointer to that node and free up the memory for that.

Case 2: The node has one child. In that case, you can connect the parent and child of that node and delete the pointer to and from the node you want to delete.

Case 3: The node has 2 children. Here is where I'm having a bit of a problem. Let's assume we have the following example.

enter image description here

I want to delete the node "4". To do this, I go to the largest integer node on its right side, i.e. "5" and swap their values. So 4 becomes 5 and 5 becomes 5. The I can simply delete the node "5" and I'll be done. Is this approach correct or am I missing anything?

$\endgroup$
  • $\begingroup$ I think you forgot to mention it is a binary search tree. $\endgroup$ – Navjot Waraich Jan 6 at 17:28
1
$\begingroup$

Your approach works in your example, but not in general. For example, if the node with key 5 also has a left child with key 4.5, it will not be correct because the resulting tree is not a binary search tree anymore.

You have to replace the node to be deleted (4) not with its right child (5), but with its successor in the key ordering, which is the least-valued node in its right sub-tree (in your example, that is indeed 5, but in my example it would be 4.5, not 5).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.