C++ Binary search tree delete issue

Question

I am new on C++. My background is from PHP and C#. I implement Binary search tree in VC++ in Visual Studio 2005

All operations are fine, I am facing the problem with delete in one particular scenario, i.e. when I try to delete head twice or more times.

Proposed strategy is

1. Find minimum in the right sub tree
2. Replace the node you want to delete with minimum
3. delete minimum

In my code 8 is on the top, when I delete top, first time, than 11 become top from right sub tree, If I delete any other node, code is working fine, but if I delete top again(after deletion of 8 now it is 11) I got following error

Windows has triggered a breakpoint in BinarySearchTreeByList.exe.

This may be due to a corruption of the heap, and indicates a bug in >BinarySearchTreeByList.exe or any of the DLLs it has loaded.

The output window may have more diagnostic information

Following is complete code

#include "stdafx.h"
#include <stdio.h>
#include <tchar.h>
#include <list>
#include <iostream>

typedef struct node
{
    node* left;
    node* right;
    node* parent;
    int val;
};

using namespace std;

void insert_node(node** iterate, int newVal, node* newParent);
void traverse(node* iterate);
void del(node** iterate, int newVal, char direction);


void traverse(node* iterate)
{
    if(iterate != NULL)
    {
        traverse(iterate->left);
        printf("%d ",iterate->val);
        traverse(iterate->right);
    }
}


void del(node** iterate, int newVal, char direction)
{

    if((*iterate) == NULL)
        return;

    if((*iterate)->val == newVal)
    {
        if((*iterate)->left == NULL && (*iterate)->right == NULL)
        {
            if(direction == 't')
            {
                node* deleted = *iterate;
                *iterate = NULL;
                free(deleted);
            }

            if(direction == 'l')
            {
                node* deleted = (*iterate)->parent->left;
                (*iterate)->parent->left = NULL;
                free(deleted);
            }

            if(direction == 'r')
            {
                node* deleted = (*iterate)->parent->right;
                (*iterate)->parent->right = NULL;
                free(deleted);
            }

            return;
        }

        if((*iterate)->left == NULL)
        {
            if(direction == 't')
            {
                node* deleted = *iterate;
                *iterate = (*iterate)->right;
                (*iterate)->parent = NULL;
                free(deleted);
            }

            if(direction == 'l')
            {
                node* deleted = *iterate;
                (*iterate)->parent->left = (*iterate)->right;
                free(deleted);
            }

            if(direction == 'r')
            {
                node* deleted = *iterate;
                (*iterate)->parent->right = (*iterate)->right;
                free(deleted);
            }

            return;
        }

        if((*iterate)->right == NULL)
        {
            if(direction == 't')
            {
                node* deleted = *iterate;
                *iterate = (*iterate)->left;
                (*iterate)->parent = NULL;
                free(deleted);
            }

            if(direction == 'l')
            {
                node* deleted = *iterate;
                (*iterate)->parent->left = (*iterate)->left;
                free(deleted);
            }

            if(direction == 'r')
            {
                node* deleted = *iterate;
                (*iterate)->parent->right = (*iterate)->left;
                free(deleted);
            }

            return;
        }

        node* findmin = (*iterate)->right;

        int minVal = 0;

        while(findmin != NULL)
        {
            minVal = findmin->val;
            findmin = findmin->left;
        }

        (*iterate)->val = minVal;

        del(&((*iterate)->right), minVal, 'r');

        return;
    }

    if(newVal < (*iterate)->val)
        del(&((*iterate)->left) ,newVal, 'l');
    else
        del(&((*iterate)->right) ,newVal, 'r');

}


void insert_node(node** iterate, int newVal, node* newParent)
{
    if(*iterate == NULL)
    {
        node* newNode = (node*)malloc(sizeof(node));

        newNode->val = newVal;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->parent = newParent;

        *iterate = newNode;

        return;
    }

    if(newVal < (*iterate)->val)
        insert_node(&((*iterate)->left) , newVal, *iterate);
    else
        insert_node(&((*iterate)->right) , newVal, *iterate);
}

int main()
{
    node* iterate = NULL;

    insert_node(&iterate, 8, NULL);
    insert_node(&iterate, 15, NULL);
    insert_node(&iterate, 4, NULL);
    insert_node(&iterate, 2, NULL);
    insert_node(&iterate, 1, NULL);
    insert_node(&iterate, 3, NULL);
    insert_node(&iterate, 7, NULL);
    insert_node(&iterate, 6, NULL);
    insert_node(&iterate, 11, NULL);
    insert_node(&iterate, 22, NULL);
    insert_node(&iterate, 12, NULL);
    insert_node(&iterate, 13, NULL);    


    traverse(iterate);
    printf("\n\n");

    del(&iterate, 8, 't');
    del(&iterate, 22, 't');
    del(&iterate, 7, 't');
    del(&iterate, 11, 't');

    printf("\n\n");
    traverse(iterate);

    cin.clear();
    cin.ignore(255, '\n');
    cin.get(); 

}

Thank you for your help

Answer 1

Your problem is when you delete a node you set the child node pointer of the deleted parent to the deleted node's child, but you don't set the deleted parent's child pointer to the deleted node's child.

For instance:

    if(direction == 'l')
    {
        node* deleted = *iterate;
        (*iterate)->parent->left = (*iterate)->right;
        deleted->right->parent = deleted->parent;
        free(deleted);
    }

You were missing the line deleted->right->parent = deleted->parent;, I added it. There are a few more places in the code you should fix in the same manner.

Answer 2

Your problem is that you don't update the parents when you delete a node with children. The parent field is only assigned when you insert a node, and hence you have a well-defined tree. You also set it in some cases, e.g. when there is only one child and the direction is 't'.

You break the tree when you start jiggling around nodes without updating the parents of the children of the deleted nodes in the 'l' and 'r' cases.