Deleting the leaf nodes of a binary search tree

[maraghuram]

I am trying to delete the leaf nodes in a bst which i have created non-recursively. The problem is when i am trying to delete the leaf node i hit a segmentation fault and i have no clue as to why its happening. I believe the code which i have commented is causing the problem. Is it wrong or are there any other ways of deleting any node from the bst ??

 #include <stdio.h>
 #include <stdlib.h>

 struct BSTnode
{
 int data;
 struct BSTnode *left,*right,*parent;

};

 typedef struct BSTnode node;

 void insert(node **root,int val)
{
  node *ptr,*newptr;

  newptr=(node *)malloc(sizeof(node));
  newptr->left=NULL;
  newptr->right=NULL;
  newptr->parent=NULL;
  newptr->data=val;

  if((*root)==NULL)
 {
   (*root)=newptr;
   return;
 }

  ptr=(*root);  

  while(ptr!=NULL && ptr->data!=val)
 {
   if(ptr->data >val )
  {
    if(ptr->left!=NULL)
     ptr=ptr->left;
    else
   {
     ptr->left=newptr;
     newptr->parent=ptr;
     break;
   }
  } 
   else
  {
    if(ptr->right!=NULL)
     ptr=ptr->right;
    else
   {
     ptr->right=newptr;
     newptr->parent=ptr;
     break;
   }
  }
 }

}

 void deleteLeaf(node **root)
{
  node *leafParent=NULL;

  if((*root)->left!=NULL)
   deleteLeaf(&((*root)->left));

  if((*root)->right!=NULL)
   deleteLeaf(&((*root)->right));


  if((*root)->left==NULL && (*root)->right==NULL)
 {

 /*  leafParent=(*root)->parent;

   if(leafParent->left==(*root))
    leafParent->left=NULL;
   else
    leafParent->right=NULL;
 */

  free(*root);
 }
}

 void inorder(node *root)
{
  if(root->left!=NULL)
   inorder(root->left);

  printf(" %d ", root->data);

  if(root->right!=NULL)
   inorder(root->right);
}

 main()
{
 node *root=NULL;
 int i,n,val;

 printf("\n How many elements ?");
 scanf("%d",&n);

 for(i=0;i<n;++i)
{
 scanf("%d",&val);
 insert(&root,val);

}

 printf("\n Inorder traversal : ");
 inorder(root);

 deleteLeaf(&root);
 printf("\n Inorder traversal : ");
 inorder(root);
}

[deceptikon]

You're correct, in a manner of speaking. The problem is that you haven't told the recursive chain higher up that the desired leaf was deleted. What happens if by deleting a leaf, you've created a new leaf? And what happens if that occurs all the way up to and including the root of the tree?

[Gonbe]

People are using the term "leaf" differently.. A leaf node would be a node without any children in my book. I assume you just want to delete any node from your tree, meaning you could delete the leafs too if you wanted.

I am trying to delete the leaf nodes in a bst which i have created non-recursively.

It doesn't matter how you created the tree. In the example below I delete a node recursively for example.

#include <stdio.h>
#include <stdlib.h>

struct BSTnode
{
    int data;
    struct BSTnode *left,*right,*parent;
};

typedef struct BSTnode node;

void insert(node **root, int val)
{
    node *ptr, *newptr;

    newptr=(node *)malloc(sizeof(node));

    newptr->left    =NULL;
    newptr->right   =NULL;
    newptr->parent  =NULL;
    newptr->data    =val;

    if((*root)==NULL)
    {
        (*root) = newptr;
        return;
    }

    ptr = (*root);

    // Remark: Disallowing duplicates is intentional I guess.
    while(ptr != NULL && ptr->data != val)
    {
        if(ptr->data > val )
        {
            if(ptr->left != NULL)
                ptr = ptr->left;
            else
            {
                ptr->left = newptr;
                newptr->parent = ptr;
                break;
            }
        }
        else
        {
            if(ptr->right!=NULL)
                ptr = ptr->right;
            else
            {
                ptr->right = newptr;
                newptr->parent = ptr;
                break;
            }
        }
    }
}

//Changed: Added this helper function.
node* getLowestNode(node* root)
{
    if (root != NULL)
    {
        while (root->left != NULL)
        {
            root = root->left;
        }
    }
    return root;
}


// Changed: Added a value parameter. The first one found will be deleted.
void deleteLeaf(node **root, int value)
{
    node* replacement = NULL;
    node* deletedNode = NULL;

    // The supplied node is NULL. Nothing to do!
    if (root == NULL || *root == NULL)
        return;

    // We found our node!
    else if ((*root)->data == value)
    {
        deletedNode = (*root);

        //Obtain the smallest node in the right subtree, as this will replace this node. (understanding this is key)
        replacement = getLowestNode(deletedNode->right);

        // There is no right tree..
        if (replacement == NULL)
        {
            // ..so just replace it with the left tree.
            // Remark: having this flag is anoying. Can be rewritten to be different..
            (*root)         = deletedNode->left;
            (*root)->parent = deletedNode->parent;
        }
        // A replacement node was found.
        else
        {
            // Update the parent reference of the childs.
            if ((*root)->left  != NULL) (*root)->left ->parent = replacement;
            if ((*root)->right != NULL) (*root)->right->parent = replacement;

            // This replacement node might have childs on it's right tree. (but none on the left)
            // These are assigned to the parent's left subtree.
            replacement->parent->left = replacement->right;
            if (replacement->right != NULL) replacement->right->parent = replacement->parent;

            // Replace our node with the replacement node.
            replacement->right = (*root)->right;
            replacement->left  = (*root)->left;
            replacement->parent = (*root)->parent;

            (*root) = replacement;
        }

        // Replacements done. Free the deleted node.
        free(deletedNode);
    }
    else if ((*root)->data < value)
    {
        // Subproblem: delete the node from the right subtree.
        deleteLeaf(&((*root)->right), value);
    }
    else
    {
        // Subproblem: delete the node from the left subtree.
        deleteLeaf(&((*root)->left), value);
    }
}

void inorder(node *root)
{
    // Changed: Don't attempt to dereference a null pointer.
    if (root != NULL)
    {
        if(root->left!=NULL)
        inorder(root->left);

        printf(" %d ", root->data);

        if(root->right!=NULL)
        inorder(root->right);
    }
}

// Changed: proper main header
int main(void)
{
    node *root = NULL;
    int i, n, val;

    printf("\n How many elements ?");
    scanf("%d",&n);

    for(i = 0; i < n; ++i)
    {
        scanf("%d",&val);
        insert(&root,val);
    }

    printf("\n Inorder traversal : ");
    inorder(root);

    //Changed: Added some delete calls.
    printf("\n Deleting node 3.");
    deleteLeaf(&root, 3);
    printf("\n Deleting node 5.");
    deleteLeaf(&root, 5);
    printf("\n Deleting node 7.");
    deleteLeaf(&root, 7);

    printf("\n Inorder traversal : ");
    inorder(root);

    // Changed: return
    return 0;
}

Example:

How many elements ?10
10 9 8 7 6 5 4 3 2 1

Inorder traversal : 1 2 3 4 5 6 7 8 9 10
Deleting node 3.
Deleting node 5.
Deleting node 7.
Inorder traversal : 1 2 4 6 8 9 10

I hope this is what you meant. Also note that your tree will not hold duplicates and you don't really need to keep track of the parent for each node. Removig the parent probably make things easier. Currently I shift pointers but because they only hold an integer i could swap that instead, would be easier too. But this is more future-proof.

-edit-
I didn't really check why your code crashes but something that immediatelystands out is that you call delete recursively but don't seem to check for NULL pointers received. Your "inorder" function also didn't check for NULL pointers. I'm not sure what you wanted your function to do in the first place as you don't ask for a value to identify the node you want to delete. Did you just want to delete the tree in it's entirety? If you can't fix your code based on my example above, let me know and I'll look at it more closely.