Showing posts with label Delete Node. Show all posts
Showing posts with label Delete Node. Show all posts

Tuesday, 10 September 2013

Saturday, 7 September 2013

Showing posts with label Delete Node. Show all posts
Showing posts with label Delete Node. Show all posts

Tuesday, 10 September 2013

Delete a node from the binary search tree


Code for Program to insert and delete a node from the binary search tree in C Programming





#include <stdio.h>

#include <stdlib.h>

#define TRUE 1
#define FALSE 0

   struct btreenode *leftchild ;
  struct btreenode


{
   int data ;
    struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **,
                struct btreenode **, int * ) ;
void inorder ( struct btreenode * ) ;

void main( )
{
    struct btreenode *bt ;
    int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;

    bt = NULL ;  /* empty tree */


    

    while ( i <= 8 )
    {
        insert ( &bt, a[i] ) ;
        i++ ;
    }
    
    printf ( "Binary tree before deletion:\n" ) ;
    inorder ( bt ) ;

    delete ( &bt, 10 ) ;
    printf ( "\nBinary tree after deletion:\n" ) ;
    inorder ( bt ) ;

    delete ( &bt, 14 ) ;
    printf ( "\nBinary tree after deletion:\n" ) ;
    inorder ( bt ) ;

    delete ( &bt, 8 ) ;
    printf ( "\nBinary tree after deletion:\n" ) ;
    inorder ( bt ) ;

    delete ( &bt, 13 ) ;
    printf ( "\nBinary tree after deletion:\n" ) ;
    inorder ( bt ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
    if ( *sr == NULL )
    {
        *sr = malloc ( sizeof ( struct btreenode ) ) ;

        ( *sr ) -> leftchild = NULL ;
        ( *sr ) -> data = num ;
        ( *sr ) -> rightchild = NULL ;
    }
    else/* search the node to which new node will be attached */

    {
        /* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
            insert ( &( ( *sr ) -> leftchild ), num ) ;
        else/* else traverse to right */

            insert ( &( ( *sr ) -> rightchild ), num ) ;
    }
}

/* deletes a node from the binary search tree */
void delete ( struct btreenode **root, int num )
{
    int found ;
    struct btreenode *parent, *x, *xsucc ;

    /* if tree is empty */
if ( *root == NULL )
    {
        printf ( "\nTree is empty" ) ;
        return ;
    }

    parent = x = NULL ;

    /* call to search function to find the node to be deleted */

    search ( root, num, &parent, &x, &found ) ;

    /* if the node to deleted is not found */
if ( found == FALSE )
    {
        printf ( "\nData to be deleted, not found" ) ;
        return ;
    }

    /* if the node to be deleted has two children */
if ( x -> leftchild != NULL && x -> rightchild != NULL )
    {
        parent = x ;
        xsucc = x -> rightchild ;

        while ( xsucc -> leftchild != NULL )
        {
            parent = xsucc ;
            xsucc = xsucc -> leftchild ;
        }

        x -> data = xsucc -> data ;
        x = xsucc ;
    }

    /* if the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
    {
        if ( parent -> rightchild == x )
            parent -> rightchild = NULL ;
        else
            parent -> leftchild = NULL ;

        free ( x ) ;
        return ;
    }

    /* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
    {
        if ( parent -> leftchild == x )
            parent -> leftchild = x -> rightchild ;
        else
            parent -> rightchild = x -> rightchild ;

        free ( x ) ;
        return ;
    }

    /* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
    {
        if ( parent -> leftchild == x )
            parent -> leftchild = x -> leftchild ;
        else
            parent -> rightchild = x -> leftchild ;

        free ( x ) ;
        return ;
    }
}

/*returns the address of the node to be deleted, address of its parent and
   whether the node is found or not */
void search ( struct btreenode **root, int num, struct btreenode **par, struct
        btreenode **x, int *found )
{
    struct btreenode *q ;

    q = *root ;
    *found = FALSE ;
    *par = NULL ;

    while ( q != NULL )
    {
        /* if the node to be deleted is found */
if ( q -> data == num )
        {
            *found = TRUE ;
            *x = q ;
            return ;
        }

        *par = q ;

        if ( q -> data > num )
            q = q -> leftchild ;
        else
            q = q -> rightchild ;
    }
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
    if ( sr != NULL )
    {
        inorder ( sr -> leftchild ) ;

        /* print the data of the node whose leftchild is NULL or the path  has
            already been traversed */

        printf ( "%d\t", sr -> data ) ;

        inorder ( sr -> rightchild ) ;
    }
}

Delete a node from binary Tree



To delete a node from Binary tree if :
1.if the node to be deleted has no child.
2.if node has two children.
3.if the node has only right child.
4.if the node has only left child.
#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *left;
    struct node *right;
    
};

void insert(struct node **,int);
void postorder(struct node *);
void delete(struct node **,int,struct node **);

int main(){
    struct node *s;
    s=NULL;
    insert(&s,11);
    insert(&s,13);
    postorder(s);
    printf("\n");
    delete(&s,11,NULL);
    printf("\n");
    postorder(s);
    return 0;
}

void insert(struct node **s,int num){
    if((*s)==0){
        (*s)=(struct node *)malloc(sizeof(struct node));
        (*s)->left=0;
        (*s)->data=num;
        
        (*s)->right=0;
    }
  
    else if(num<((*s)->data)){
        insert(&((*s)->left),num);
    }
  
    else if(num>((*s)->data)){
        insert(&((*s)->right),num);
    }

      
}
 void postorder(struct node *s){
     
        
        if(s!=NULL){
            
            postorder(s->left);
            postorder(s->right);
            printf("%d ",s->data);
        }else
        return;
     }
void delete(struct node **s,int num,struct node **f){
    struct node *temp;
    if((*s)->data==num){
        if(((*s)->left==NULL) && ((*s)->right==NULL)){
        temp=&(*s);
        free(*s);
        (*s)=NULL;
        }
//only delete if right node present and left should be null
        else if(((*s)->left==NULL) && ((*s)->right!=NULL)){
            free(*s);
            (*s)=(*s)->right;
        }

else if(((*s)->left!=NULL) && ((*s)->right==NULL)){
            free(*s);
            (*s)=(*s)->left;
        }

    }    
        
    }
output
$demo
13 11 

13 


Saturday, 7 September 2013

Delete N nodes after M nodes of a linked list




Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same till end of the linked list.
Difficulty Level: Rookie
Examples:
Input:
M = 2, N = 2
Linked List: 1->2->3->4->5->6->7->8
Output:
Linked List: 1->2->5->6

Input:
M = 3, N = 2
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:
Linked List: 1->2->3->6->7->8

Input:
M = 1, N = 1
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:  
Linked List: 1->3->5->7->9
The main part of the problem is to maintain proper links between nodes, make sure that all corner cases are handled. Following is C implementation of function skipMdeleteN() that skips M nodes and delete N nodes till end of list. It is assumed that M cannot be 0.
// C program to delete N nodes after M nodes of a linked list
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct node
{
    int data;
    struct node *next;
};
/* Function to insert a node at the beginning */
void push(struct node ** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    /* put in the data  */
    new_node->data  = new_data;
    /* link the old list off the new node */
    new_node->next = (*head_ref);
    /* move the head to point to the new node */
    (*head_ref)  = new_node;
}
/* Function to print linked list */
void printList(struct node *head)
{
    struct node *temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
// Function to skip M nodes and then delete N nodes of the linked list.
void skipMdeleteN(struct node  *head, int M, int N)
{
    struct node *curr = head, *t;
    int count;
    // The main loop that traverses through the whole list
    while (curr)
    {
        // Skip M nodes
        for (count = 1; count<M && curr!= NULL; count++)
            curr = curr->next;
        // If we reached end of list, then return
        if (curr == NULL)
            return;
        // Start from next node and delete N nodes
        t = curr->next;
        for (count = 1; count<=N && t!= NULL; count++)
        {
            struct node *temp = t;
            t = t->next;
            free(temp);
        }
        curr->next = t; // Link the previous list with remaining nodes
        // Set current pointer for next iteration
        curr = t;
    }
}
// Driver program to test above functions
int main()
{
    /* Create following linked list
      1->2->3->4->5->6->7->8->9->10 */
    struct node* head = NULL;
    int M=2, N=3;
    push(&head, 10);
    push(&head, 9);
    push(&head, 8);
    push(&head, 7);
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    printf("M = %d, N = %d \nGiven Linked list is :\n", M, N);
    printList(head);
    skipMdeleteN(head, M, N);
    printf("\nLinked list after deletion is :\n");
    printList(head);
    return 0;
}
Output:
M = 2, N = 3
Given Linked list is :
1 2 3 4 5 6 7 8 9 10

Linked list after deletion is :
1 2 6 7
Time Complexity: O(n) where n is number of nodes in linked list.