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?