Binary Tree Deletion

[squirellplaying]

public TreeNode deleteHelper(TreeNode node, Integer target)
// pre : node points to a non-empty binary search tree
// post: deletes a node with data equal to target, if present,
// preserving binary search tree property
{
if (node == null) //Make sure the node is not null
throw new NoSuchElementException();

else if (node.compareTo(target) == 0)
{
return deleteTargetNode(node);//This is the node to delete
}
else if (node.compareTo(target) < 0) //The node to delete is to the LEFT of the current node, so set the LEFT node to what ever is returned
{
node.setLeft(deleteHelper(node.getLeft(), target));
return node;
}
else //target.compareTo(root.getValue()) > 0
{
node.setRight(deleteHelper(node.getRight(), target));//The node to delete is to the RIGHT of the current node, so set the RIGHT node to what ever is returned
return node;
}
}

private TreeNode deleteTargetNode(TreeNode target)
// pre : target points to node to be deleted
// post: target node is deleted preserving binary search tree property
{
if (target.getRight() == null)
{
return target.getLeft(); //Return the left value to get set as the "nextLeft"
}
else if (target.getLeft() == null)
{
return target.getRight();//Return the right value to get set as the "nextRight"
}
else if (target.getLeft().getRight() == null) //No Idea from this point on ***************
{
target.setValue(target.getLeft().getValue());
target.setLeft(target.getLeft().getLeft());
return target;
}
else // left child has right child
{
TreeNode marker = target.getLeft();
while (marker.getRight().getRight() != null)
marker = marker.getRight();

target.setValue(marker.getRight().getValue());
marker.setRight(marker.getRight().getLeft());
return target;
}
}

This code deletes a value from a binary tree. The curriculum basicly said, here's the code to use, use it. But I have no idea how it works. I've commented what I think it's doing. The part that is stared is the point I don't understand.

[jkd]

That code looks mean. Attached is a naive way of deleting nodes. Perhaps this is what is going on? Or maybe the deletion code given dumps all the nodes back into the tree individually. The latter helps keep the tree balanced, but the png I am attaching gives a faster deletion algorithm.

[squirellplaying]

Yea, I understand mostly what's suppose to happen, but I don't know how to implement it.

[jkd]

nodeToDelete.left.findMaxChildNode().right = nodeToDelete.right;

essentially as easy as that. You'll need a reference to nodeToDelete's parent node in order to remove the node correctly (set the parent's reference to it to null).

findMaxChildNode() just always takes the right branch, and returns the deepest one before it hits null.