CODEWITHSUNDEEP
c#recursionbinary-search-tree
user9681559
user9681559

Reputation: 55

Binary-Search-Tree's remove function doesn't work for 2 child nodes

I'm learning about Binary Search Trees and Recursion. I'm able to get expected results with leaf and single child nodes. However, whenever I try to delete a node with 2 child nodes but am not receiving the expected result. When deleting the rootNode (12), How is it possible that the rootNode is being set as 18... since 18 is the value of the root's right child's right node?

/* Using Pre-Order Traversal
* Original Tree: [12,7,3,7,14,18]
* Expected Result: [14,7,3,7,18]
* Result Tree: [18,7,3,7,18] */

public void DeleteNode(Node rootNode, int deleteValue)
{
    SearchBinaryTree(DeleteNodeHelper, rootNode, deleteValue);
}

public void DeleteNodeHelper(Node node)
{
    if(node != null)
    {
        // 0 child? unlink the node from its parent
        if (node.Left == null && node.Right == null)
        {
            node.Value = 0;
            node.Name = "deleted";
            node.Left = null;
            node.Right = null;
        }
        // 2 child? replace root node with right child's left-most value
        if (node.Left != null && node.Right != null)
        {
            Node rootNodeReplacement = FindLeftMostNode(node.Right);
            SearchBinaryTree(DeleteNodeHelper, node.Right, rootNodeReplacement.Value);
            node.Value = rootNodeReplacement.Value;
        }
        //1 child? replace root node with only child
        else
        {
            node.Value = node.Left != null ? node.Left.Value : node.Right.Value;
            node.Name = node.Left != null ? node.Left.Name : node.Right.Name;
            node.Left = null;
            node.Right = null;
        }
    }
}

public void SearchBinaryTree(Action<Node> action, Node node, int searchValue)
{
    if (node != null)
    {
        if ( node.Value == searchValue)
        {
            action.Invoke(node);
        }
        if (node.Value < searchValue)
        {
            SearchBinaryTree(action, node.Right, searchValue);
        }
        if (node.Value > searchValue)
        {
            SearchBinaryTree(action, node.Left, searchValue);
        }     
    }
}

public Node FindLeftMostNode(Node node)
{
    while (node.Left != null)
    {
        node = node.Left;
    }
    return node;
}

Upvotes: 0

Views: 52

Answers (1)

user9681559
user9681559

Reputation: 55

Figured it out. I had two lines of code swapped. I tried to delete the right-child's left-most node before I updated the root node.

public void DeleteNodeHelper(Node node)
{
    if (node != null)
    {
        // 0 child? unlink the node from its parent
        if (node.Left == null && node.Right == null)
        {
            node.Value = 0;
            node.Name = "deleted";
            node.Left = null;
            node.Right = null;
        }
        // 2 child? replace root node with right child's left-most value
        if (node.Left != null && node.Right != null)
        {
            Node rootNodeReplacement = FindLeftMostNode(node.Right);
            node.Value = rootNodeReplacement.Value; //this line was swapped with the one below
            SearchBinaryTree(DeleteNodeHelper, node.Right, rootNodeReplacement.Value);
        }
        //1 child? replace root node with only child
        else
        {
            node.Value = node.Left != null ? node.Left.Value : node.Right.Value;
            node.Name = node.Left != null ? node.Left.Name : node.Right.Name;
            node.Left = null;
            node.Right = null;
        }
    }
}

Upvotes: 1

Related Questions