C binary search tree deletion implementation

Question

I am trying to implement the deletion function for a binary search tree in C, however I am running into problems.

I have the following structs for the tree and the nodes

typedef struct {
    double value;

    struct Node *parent;
    struct Node *right_child;
    struct Node *left_child;
} Node;

typedef struct {
    struct Node *root;
} Tree;

I also have an in-order traversal function

void inOrderTraversalNode(Node *n) {

    if (n != NULL) {

        inOrderTraversalNode(n->left_child);
        printf("%f\n", n->value);
        inOrderTraversalNode(n->right_child);
    }
}

A subtree minimum function

Node * minimum(Node *n) {

    while (n->left_child != NULL) {
        n = n->left_child;
    }

    return n;
}

and a transplant function

void transplant(Tree *t, Node *u, Node *v) {

    Node *p = u->parent;

    //replace u's parent's child pointer to v
    if (p == NULL) {
        t->root = v;
    } else if (u == p->left_child) {
        p->left_child = v;
    } else {
        p->right_child = v;
    }

    //set v's parent pointer to u's parent
    if (v != NULL) {
        v->parent = p;
    }
}

And finally I have the delete function

void delete(Tree *t, Node *z) {

    //if node z has no left subtree, replace z with right subtree and vice-versa.
    if (z->left_child == NULL) {
        transplant(t, z, z->right_child);

    } else if (z->right_child == NULL) {
        transplant(t, z, z->left_child);
    } else {
        Node *y = minimum(z->right_child);

        if (y->parent != z) {
            transplant(t, y, y->right_child);

            Node *y_right_child = y->right_child;

            y_right_child = z->right_child;
            y_right_child->parent = y;
        }
        transplant(t, z, y);

        Node *y_left_child = y->left_child;

        y_left_child = z->left_child;
        y_left_child->parent = y;
    }

}

However when I run the following code in main

int main(void) {

        Node n1;
        Node n2;
        Node n3;
        Node n4;
        Node n5;
        Node n6;
        Node n7;
        Node n8;

        n1.value = 4;
        n1.parent = NULL;
        n1.left_child = &n2;
        n1.right_child = &n5;

        n2.value = 2;
        n2.parent = &n1;
        n2.left_child = &n3;
        n2.right_child = &n4;

        n3.value = 1;
        n3.parent = &n2;
        n3.left_child = NULL;
        n3.right_child = NULL;

        n4.value = 3;
        n4.parent = &n2;
        n4.left_child = NULL;
        n4.right_child = NULL;

        n5.value = 6;
        n5.parent = &n1;
        n5.left_child = &n6;
        n5.right_child = &n7;

        n6.value = 5;
        n6.parent = &n5;
        n6.left_child = NULL;
        n6.right_child = NULL;

        n7.value = 7;
        n7.parent = &n5;
        n7.left_child = NULL;
        n7.right_child = NULL;


        Tree t;

        t.root = &n1;

        printf("In order traversal\n");
        inOrderTraversalNode(t.root);

        printf("Delete node\n");
        delete(&t,&n1);
        inOrderTraversalNode(t.root);


        return EXIT_SUCCESS;
    }

It returns 1,2,3,4,5,6,7 for the first traversal. But it returns 1,2,3,4,7 for the second traversal after deleting n5 which is incorrect because it misses the n6 node containing 5. I do not understand why this is happening. I have inserted some print statements in the delete function and the n7 node is adding the n6 node as its left child, but for some reason it doesn't get printed during the traversal.

Can you post the rest of `main`, so that there is a complete program that can be compiled and run? It will be easier to find the bug by running with a debugger than by staring at the code. — Nate Eldredge, Sep 19 '15 at 02:53
Suspicious code in `delete`: `Node *y_right_child = y->right_child; y_right_child = z->right_child;` You initialize the variable and then immediately assign it another value? — Nate Eldredge, Sep 19 '15 at 03:20
For what it's worth, when I run it, after running `delete` the tree consists *only* of a single node with value `5`. — Nate Eldredge, Sep 19 '15 at 03:23
I was trying to do ```y->right_child->parent=y``` but this gives the error ```error: incomplete definition of type 'struct Node'``` — user1893354, Sep 19 '15 at 03:54
The first line should say `typedef struct Node {`. There must be a question here on SO explaining why that is... You should have got a ton of warnings without it. — Nate Eldredge, Sep 19 '15 at 03:58

score 1 · Accepted Answer · answered Sep 19 '15 at 03:28

This code caught my attention:

        Node *y_right_child = y->right_child;

        y_right_child = z->right_child;
        y_right_child->parent = y;

You assign a value to variable y_right_child, and then you immediately replace it with a different value. What you intend to do, it appears, is transfer node z's right child to node y. That would be this:

        y->right_child = z->right_child;
        y->right_child->parent = y;

You don't need to remember or modify y's original right child at that point, because that was already handled via function transplant().

There is a similar issue with the other child-transfer code:

    Node *y_left_child = y->left_child;

    y_left_child = z->left_child;
    y_left_child->parent = y;

Again, you assign a value to the variable, and then immediately replace it. What you appear really to want is this:

    y->left_child = z->left_child;
    y->left_child->parent = y;

Note that because node y started out as the minimum value from its subtree, you can be certain that y->left_child is initially NULL.

I see. I actually had this at first but the problem is that ```y->right_child->parent``` gives me the error ```error: incomplete definition of type 'struct Node'``` — user1893354, Sep 19 '15 at 03:39

score 1 · Answer 2 · edited May 23 '17 at 12:14

As your code stands, the type struct Node is not declared or defined anywhere. The typedef at the top of your code doesn't accomplish this; it defines a different type called Node. See typedef struct vs struct definitions. This should have caused a ton of warnings in your compilation. Don't ignore them!

It also seems to have been the indirect cause of the real bug. In delete you have the code

        Node *y_right_child = y->right_child;

        y_right_child = z->right_child;
        y_right_child->parent = y;

which is clearly not the right thing. You want to change the right child pointer of y. But when you wrote what you really want:

        y->right_child = z->right_child;
        y->right_child->parent = y;

you got an error because y->right_child is of the undefined type struct Node * and therefore can't be dereferenced. Rather than fix this properly, you introduced the local variable y_right_child, which at least made the code compile. But what good is code that compiles, if it doesn't work? Assigning to y_right_child just changes the value of the local variable; it doesn't change the value of the pointer y->right_child itself.

Changing the very first line to typedef struct Node { causes struct Node to be defined as what you want (and the typedef Node is defined as the same type). Then changing y_right_child to y->right_child and removing the variable y_right_child altogether, and doing the same for y->left_child, the delete works as intended.

C binary search tree deletion implementation

2 Answers2