Delete a node from dynamic Binary Search Tree using iteration in C (Homework)

Viewed 39

Given:

typedef int element;
typedef struct node
{
    element data;
    struct node *left,*right;
} *Btree;
typedef Btree BST;

Write a recursive function that delete an element e from a BST. Return 0 if unsuccessful, 1 if successful.

You may use the following function in your code:

BST *find(BST *B, element e) //didn't use it since I didn't find the need for it, although since it's given, it probably is useful

My code:

int delete_BST(BST *B , element e)
{
    if(!(*B)) return 0;
    BST t = *B;
    while(1)
    {
        if(t->data < e) t = t->right;
        if(t->data > e) t = t->left;
        else
        {
            if(t->left && t->right)
            {
                BST maxleft = t->left;
                while(maxleft->right)
                    maxleft = maxleft->right;
                t->data = maxleft->data;
                t = t->left;
                e = maxleft->data;
            }
            else
            {
                BST temp = t;
                if(!t->left) t = t->right;
                else if(!t->right) t = t->left;
                free(temp);
                break;
            }
        }
    }
    return 1;
}

Input:

    6
   / \
  3   8
 / \
1   5
Then delete: 1, 5, 8, -5, 0, 4 and 23

Expected Result:

  6
 /
3

My Result: it's blank


my approach to this was applying the previous recursive method and transforming it to be iterative however that question had another given fucntion other than BST *find(BST *B, element e), it had BST *find(BST *B, element e) which I used to get the maximum element in the left subtree of a node to be deleted that had 2 children.

My Recursive Code:

int delete_BST(BST *B , element e)
{
    if(!(*B)) return 0;
    if((*B)->data < e) return delete_BST(&(*B)->right, e);
    else if((*B)->data > e) return delete_BST(&(*B)->left, e);
    else
    {
        BST temp;
        if((*B)->left && (*B)->right)
        {
            temp = max_BST((*B)->left);
            (*B)->data = temp->data;
            delete_BST(&((*B)->left), temp->data);
        }
        else
        {
            temp = *B;
            if(!(*B)->left) *B = (*B)->right;
            else if(!(*B)->right) *B = (*B)->left;
            free(temp);
        }   
    }
    return 1;
}

so what's wrong with the iterative solution and how can i fix it?

0 Answers
Related