Binary tree deletion algorithm

aijazbaig1 · #1 29-Apr-2009, 03:56

Hello,
Ive been trying to write a program to delete a node from a binary tree. The algorithm is pretty simple for a node with no children (leaf) and a node with one child. However for a node with 2 children, heres what the problem is (what the text says so atleast):
When a node with 2 children is deleted, another node must take its place. However we cannot simply assign the parent of the node being deleted to one of the children of the deleted node as then the following characteristic of a binary tree doesn't hold: values in any left subtree are to be less than the value in the parent node and values in any right subtree are to be greater than the parent node.

I am having trouble understanding or rather visualizing this problem. So heres to give an example:

Shown in the picture attached is a sample binary tree in which I decide to delete node 97. If I replace it with 92 then as it shows there is no problem except that I would have to assign the right pointer of 92 to 99 and the rest takes care of itself. However when I replace 97 with 99, then in that case I have no where to shift 92 as it will be competing with 98 (since neither 92 nor 98 can be on the right side of 99). Is this the problem that the text talks about in the last paragraph?

murugaperumal · #2 27-Feb-2010, 02:13

Dear Friend,

I have attached program to delete the element in the Binary Tree

CPP / C++ / C Code:

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct tree
{
        int node  ;
         struct tree *left ;
         struct tree *right;

} ;

struct tree *new1();
struct tree *delete(struct tree * ,int );

struct tree *addtree(struct tree *p,int w )
{
        int cond;
        if(p==NULL)
        {
                p=new1();
                p->node=w;
                p->left=p->right=NULL;
        }
        else
        {
                if(p->node >= w )
                p->left=addtree(p->left,w);
        else
                p->right=addtree(p->right,w);
        }
        return p;
}

void treeprint(struct tree *p)
{
        if(p!=NULL)
        {
                treeprint(p->left);
                printf("%d \n",p->node);
                treeprint(p->right);
        }
}

struct tree *new1 (void)
{
        return(struct tree *)malloc(sizeof(struct tree));
}

int W ;

        static int i;

int MIN;
main ( int argc, char *argv[] )
{
struct tree *root = NULL;

root=addtree(root,8);
root=addtree(root,2);
root=addtree(root,10);
root=addtree(root,1);
root=addtree(root,5);
root=addtree(root,4);
root=addtree(root,9);
root=addtree(root,15);
treeprint(root);
puts("-----------------------");
printf ("Tree After deleting :\n");
delete(root,2);
treeprint(root);
                return 0;
}           

struct tree * delete(struct tree *p, int w )
{
        struct tree *buf ;

        if (p==NULL)
                return NULL ;
        else if (w < p->node )
        {
                p->left =delete(p->left ,w );
        }
        else if (w > p->node )
        {
                p->right =delete(p->right ,w ) ;
        }
        else
        {
                if (p->left !=NULL && p->right !=NULL )
                {
                        buf=p->right ;
                        p->node=buf->node ;
                        p->right= delete(p->right,p->node);
                }

             else if ( p->left == NULL )
                {
                        buf=p;
                        p=p->right;
                }
                else if (p->right == NULL )
                {
                        buf=p ;
                        p=p->left ;
                }
        }
}

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Link List In C	Peter_APIIT	C Programming Language	33	12-Jun-2008 14:33
Please Help. I have 3 Qns regarding AVL tree in data structure , Kindly give answer	syamsankar	C++ Forum	1	30-Mar-2007 09:29
can anyone help me with my tree :)	bioeng_mtm	C++ Forum	5	22-Apr-2006 13:50
printing binary search tree	nkhambal	C Programming Language	2	26-Mar-2005 04:01
Binary Tree Trouble	neufunk	C Programming Language	4	06-Dec-2004 10:52

Binary tree deletion algorithm

Re: Binary tree deletion algorithm