Berzerker Berzerker - 10 months ago 45
Java Question

java Delete a Binary Tree node containing two children

This is the last case where the node to be deleted has two children. I cant figure out what I am doing wrong . Please help.

//BTNode has two children
else if (u.getLeft() != null && u.getRight() != null){
//if node to delete is root
BTNode<MyEntry<K,V>> pred = u.getRight();

while (pred.getLeft().element() != null){
pred = pred.getLeft();

BTNode<MyEntry<K,V>> predParent = pred.getParent();
if (!hasRightChild(pred)){
predParent.setLeft(new BTNode<MyEntry<K,V>>(null,predParent,null,null));}
if (hasRightChild(pred)){
BTNode<MyEntry<K,V>> predChild = pred.getRight();

return returnValue;

ok so modify it like this ??


BTNode<MyEntry<K,V>> succParent = succ.getParent();
if (!hasLeftChild(succ)){
succParent.setRight(new BTNode<MyEntry<K,V>>(null,succParent,null,null));}
if (hasLeftChild(succ)){
BTNode<MyEntry<K,V>> predChild = succ.getLeft();

return returnValue;

Answer Source

From wikipedia:

Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

So, take for example the left children, and then find the rightmost leaf in that subtree, then replace the information of the node to delete with that of the leaf, and then delete that leaf easily.

You might want to create a function that returns the rightmost leaf from a subtree.