This project is read-only.

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


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):


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