1
Vote

Lost all left subtrees in Remove method: FindParent(largestValue.Value).Right = null;

description

The Problem Code Snippet


{
        BinaryTreeNode<T> largestValue = nodeToRemove.Left;

        while (largestValue.Right != null)
        {
                largestValue = largestValue.Right;
        }

        FindParent(largestValue.Value).Right = null; //here is the problem
                
        nodeToRemove.Value = largestValue.Value;
}

What Is The Problem & When It Occurs


If we try to remove the node(marked red, 35) of a BST like this(the attachments contains the same image):

Image

We simply find the largest node within the left subtree of the red-marked node, that is, the most right-aligned node(marked blue, 32), then delete this node and replace the red-marked node with the value of this one(as it shows by the blue arrow). The way we delete the blue-marked node, however, is a mistake.

We simply set its parent's(marked yellow, 30) right pointer to null by:
FindParent(largestValue.Value).Right = null;
And lost all the left subtrees of the blue-marked node, wrapped by the green rectangle

How To Solve The Problem


Instead of simply set the parent's right pointer to null, it's better to call the Remove method recursively and delete the largestValue, just like other node:
{
        [...] //other code

        //FindParent(largestValue.Value).Right = null;
        Remove(largestValue.Value);    //call Remove recursively

        nodeToRemove.Value = largestValue.Value;
}

file attachments

comments