Delete node from BST - iterative

Hello
I have write program in c++ which delete node from BST. It work for some level.Mean it wrok well when some nodes are delte but when i delete root node program print garbage value infinite time... Here is my code

Code:

---

void del(int num)
{
        struct list *current,*pre,*target;
        current=root;
        if(current==NULL)
                return;
        while((current->left !=NULL) && (current->right!=NULL))
        {
                if(current->data==num)
                        target=current;
                if(num < current->data)
                {
                        if(current->left ==NULL)
                                break;
                        pre=current;
                        current=current->left;
                }
                else
                {
                        if(current->right==NULL)
                                break;
                        pre=current;
                        current=current->right;
                }
        }
        if(target == NULL)
                return;
        else
        {
                if(pre==NULL)
                {
                        free(current);
                        root=NULL;
                }
                else
                {
                        target->data=current->data;
                        if(pre->left==current)
                                pre->left=current->right;
                        else
                                pre->right=current->left;
                        free (current);
                }
        }
}

---

anyone help me! and also tell how can i find leaf node in BST....any idea or algorithm?

anyone help me? plzz

Have you tried using the debugger? This is an essential skill, unless of course you are one of those people who can write perfect code first time, every time. And there are very few of us around :D

The first thing to do would be check the del function works on a tree which consists solely of the root node. It is quite clear that your code will not work in this case as it accesses an uninitialized pointer.

Here is your code, with irrelevant bits deleted:

Code:

---

void del(int num)
{
        struct list *current,*pre,*target;
        current=root;
        if(current==NULL)
                return;
        while((current->left !=NULL) && (current->right!=NULL))
        {
                // while loop contents deleted...
        }
        if(target == NULL)
                return;
        else
        {
                // code deleted...
        }
}

---

If there is only one node, then current->left and current->right will both be NULL (assuming they have been initialized correctly). This means the while loop will not run, and target (and also pre) will remain uninitialized when it is checked against NULL. And derefencing a junk pointer (later in the code) means only one thing can happen - which is that anything can happen.

thanks for ans
my program not work in only some case...For example
Input data is 50,25,20,40,75,60,80 BST is created with inputted data
Now first time i delete node 75 then it display ans 50 25 20 40 80 60
Second time i delete node 20 then it display ans 50 25 40 80 60
third time i delete node 25 then ans is 50 40 80 60
fourth time i delete node root node 50 then ans 80 40 60
fifth time i delete node 80 then ans is 40 60
and last i delete node 40 at that time program display unknown symbol and also goes infinite....

Program delete root at all other case but when there are fewer node at that time problem is created.
Help me i try to do this program from several days....

Quote:

---

Originally Posted by CSharpque

fifth time i delete node 80 then ans is 40 60
and last i delete node 40 at that time program display unknown symbol and also goes infinite....

---

When you only have two nodes, what do you think will happen when you get to this line:

Code:

---

        while((current->left !=NULL) && (current->right!=NULL))

---

Hint: it's what I said in my previous post...

Again, have you tried the debugger?

yes i have use debugger...i have put if condition after completing while loop...

Code:

---

if(target == NULL)
        {
                if(root->left->data ==num)
                        target=root->left;

                else if(root->right->data==num)
                        target=root->right;
                else
                        return;
        }
but still program goes infinite....

---

Quote:

---

Originally Posted by CSharpque

yes i have use debugger...i have put if condition after completing while loop...

Code:

---

if(target == NULL)
        {
                if(root->left->data ==num)
                        target=root->left;

                else if(root->right->data==num)
                        target=root->right;
                else
                        return;
        }
but still program goes infinite....

---

---

That's because you still are not initializing target!
target is only given a value in the while loop. This while loop will only run if current has both a left child and a right child.

you are write i have declare target=NULL and also when node have only one child left or right at that time while loop condition become false... but i don't have any idea..can you suggest algorithm from that i can implement program...I am trying to implement this program from last 2 week but can't success..

Link'd: http://www.algolist.net/Data_structu...h_tree/Removal

Whenever you are having trouble with code, it is quite often because you are thinking about too much of the problem at a time. I would advise splitting the del function into two parts - one which finds the node corresponding to num and the other which deletes a node. E.g.:

Code:

---

void del(int num)
{
        list* node = findNode(num);
        removeNode(node);
}

---

Here, findNode() returns NULL if num isn't found, and removeNode() does nothing if called with NULL.

You will likely find a need for these functions elsewhere in the class also - so can reduce code duplication.

Quote:

---

This BST remove() function code (with iteration) works for all possible values I tested.

---

Code:

---

bool BST::remove(int x){
                node *curr, *parent;
                curr=root;
                parent=NULL;
                while(curr->data != x){
                        parent=curr;
                        if(x < curr->data)
                                curr=curr->left;
                        else if(x > curr->data)
                                curr=curr->right;
                        if(curr == NULL)
                                return false;                              /* value not found in binary search tree */
                }
                if(curr->left && curr->right){                        /* Node having two child */ /* may be root node or not */
                        node *prev = curr;
                        node* child = curr->right;
                        while(child->left != NULL){
                                prev = child;
                                child=child->left;
                        }
                        curr->data = child->data;
                        if(child->right != NULL)
                                if(prev != curr)
                                        prev->left = child->right;
                                else
                                        prev->right = child->right;
                        else
                                if(prev != curr)
                                        prev->left = NULL;
                                else
                                        prev->right = NULL;
                        delete child;
                }
                else if(parent != NULL){                        /* When Node is not root node */
                        bool left=false;
                        if(x < parent->data)
                                left=true;
                        if(curr->left == NULL && curr->right == NULL){        // leaf node //
                                if(left==true)
                                        parent->left=NULL;
                                else
                                        parent->right=NULL;
                        }
                        else if(curr->right == NULL){                                        // one child //
                        if(left==true)
                                parent->left=curr->left;
                        else
                                parent->right = curr->left;
                }
                else if(curr->left == NULL){                                                // one child //
                        if(left==true)
                                parent->left=curr->right;
                        else
                                parent->right = curr->right;
                }
                        delete curr;
                }
                else if(parent == NULL){                                                        /* Root Node having single or no child */
                        if(curr->left == NULL && curr->right == NULL)
                                root = NULL;
                        else if(curr->left == NULL)
                                root = curr->right;
                        else if(curr->right == NULL)
                                root = curr->left;
                }
        }

---

Attachment 35625Attachment 35625

For an extensive discussion I recommend Advanced Data Structures by Peter Brass. For some reason it's available on the net for free,

https://doc.lagout.org/Others/Data%2...8-09-08%5D.pdf

Search trees are presented in chapters 2 and 3. My main insight after reading was: Never ever even think of implementing a search tree yourself for use in production code :). Fortunately this isn't necessary. The standard libraries of most languages today supply implementations.