Image talk:LampFlowchart.svg

From Wikipedia, the free encyclopedia

void DeleteNode(struct node* node) {

    struct node **parentLink;

    // If there is no parent, we are a root node
    if (parent == NULL) { 
        free(node);
        return;
    }
      
    // Figure out which child of the parent we are
    if (node == node->parent->left)
        parentLink = &(node->parent->left);
    else if (node == node->parent->right) 
        parentLink = &(node->parent->right);

    // This will handle cases where both children are null.
    if (node->left == NULL) { 
        *parentLink = node->right;
        free(node); // Free any memory allocated for the node
    } else if (node->right == NULL) {
        *parentLink = node->left;
        free(node); // In C++, delete node could be used here
    } else {
        // Follow the right side of the tree until there is an empty space
        struct node* temp = node->left;
        while (temp->right != NULL) {
            temp = temp->right;
        }
        node->value = temp->value;
        DeleteNode(temp);
    }
}