Delete an object from a tree

Question

I have a Find function in order to find an element from a BST

 private Node Find(ref Node n, int e)
        {
            if (n == null)
                return null;

            if (n.Element == e)
                return n;
            if (e > n.Element)
                return Find(ref n.Right, e);
            else
                return Find(ref n.Left, e);
        }

and I use following code in order to get a node and then set this node to null.

Node x = bsTree.Find(1);
            x = null;
            bsTree.Print();

supposedly, this node should be deleted from Tree as it is set to null but it still exists in tree.

I had done this before but this time missing something and no idea what.

Answer 1

You are initialising the variable x to reference the result of calling Find, then you are reassigning the same variable to null. You haven't done anything to the tree.

To actually remove the item, you have to write some code that manipulates the tree itself. Without knowing what kind of tree you have (red-black, AVL, etc.), it is difficult to guess what that code should look like.

Answer 2

you have to get somehow the parent node of the one you want to remove. Then if the node to remove is the left one you do

parent.Left = null

if it's the right:

parent.Right = null

With this method you have to be aware that you will remove the node from the tree but also all its descendants

Answer 3

Edited:

This code removes the node from the tree, but does not return it:

private void Remove(Node n, int e)
    {
        if (n == null)
            return;

        if (e > n.Element) {
            if (e == n.Right.Element)
                n.Right = null;
            else
                Remove(n.Right, e);
        } else {
            if (e == n.Left.Element)
                n.Left = null;
            else
                Remove(n.Left, e);
        }
    }

This code also returns the Node:

private Node Remove(Node n, int e)
    {
        if (n == null)
            return null;

        if (e > n.Element) {
            if (e == n.Right.Element) {
                Node res = n.Right;
                n.Right = null;
                return res;
            } else
                return Remove(n.Right, e);
        } else {
            if (e == n.Left.Element) {
                Node res = n.Left;
                n.Left = null;
                return res;
            } else
                return Remove(n.Left, e);
        }
    }

What was wrong with the original code:

Imagine that bsTree points to the following tree:

   5

1     7

We now name the nodes a, b, and c, so they contain the values 5, 1 and 7, respectively, like

   a

b     c

a.Left now points to b and a.Right points to c.

We now want to remove the node containing 1, that is, node b. To do this, we must change the tree, such that a.Left is null and the tree will look like this:

   5

      7

Now we go through the original code step by step. First:

Node x = bsTree.Find(1);

x is declared and now points to node b. The tree is unaltered.

x = null;

x is now set to null, but a.Left still points points to b. The tree is still unaltered.

bsTree.Print();

We have now printed the tree.

Answer 4

Removing a node from a tree is a little difficult. I once wrote a remove code from a binary search tree. The code is in C, but it gives the idea clearly.

void delete_tree(node **root, int val) {

node *del = search_tree(root, val);

node *suc;

if (del == NULL) {
    printf("The value does NOT exist\n");
    return;
}

if (del->left == NULL || del->right == NULL) {
    bst_replace(root, del);
    return;
}

suc = del->right;

while (suc->left != NULL)
    suc = suc->left;

del->val = suc->val;

bst_replace(root,  suc);

return;

}

void bst_replace(node **root, node *del) {

node *child;
if (del->left == NULL)
    child = del->right;
else
    child = del->left;

if (*root == del)
    if (child != NULL) {
        child->sup = NULL;
        *root = child;
        return;
    }
    else {
        free(del);
        *root = NULL;
        return;
    }



if (del->sup->left == del)
    del->sup->left = child;
else
    del->sup->right = child;

if (child != NULL)
    child->sup = del->sup;

free(del);

return;

}

node *search_tree(node **root, int val) {

node *temp = *root;

while (temp != NULL)
    if (val < temp->val)
        temp = temp->left;
    else if (val > temp->val)
            temp = temp->right;
    else return temp;



return NULL;

}