Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
Thread Tools Search this Thread Rate Thread
Old 29-Apr-2009, 02:56
aijazbaig1's Avatar
aijazbaig1 aijazbaig1 is offline
Join Date: May 2006
Location: India
Posts: 174
aijazbaig1 has a spectacular aura aboutaijazbaig1 has a spectacular aura about

Binary tree deletion algorithm

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?
Attached Images
File Type: jpg Binary_tree.jpg (12.3 KB, 496 views)
Hope to hear from you guys!


Best Regards,
Aijaz Baig.
Old 27-Feb-2010, 02:13
murugaperumal murugaperumal is offline
New Member
Join Date: Feb 2010
Posts: 15
murugaperumal has a little shameless behaviour in the past

Re: Binary tree deletion algorithm

Dear Friend,

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

CPP / C++ / C Code:
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->node >= w )
        return p;

void treeprint(struct tree *p)
                printf("%d \n",p->node);

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;

printf ("Tree After deleting :\n");
                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 ) ;
                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 )
                else if (p->right == NULL )
                        buf=p ;
                        p=p->left ;
Last edited by LuciWiz : 27-Feb-2010 at 02:17. Reason: Please insert your C++ code between [cpp] & [/cpp] tags

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Link List In C Peter_APIIT C Programming Language 33 12-Jun-2008 13:33
Please Help. I have 3 Qns regarding AVL tree in data structure , Kindly give answer syamsankar C++ Forum 1 30-Mar-2007 08:29
can anyone help me with my tree :) bioeng_mtm C++ Forum 5 22-Apr-2006 12: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

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 22:35.

vBulletin, Copyright © 2000 - 2018, Jelsoft Enterprises Ltd.