Binary Search Tree - how to remove root

[cjjack88]

Hi, I am doing an assignment about binary search tree. I have problem with remove the root in binary tree. When i remove the root of the binary tree and I view the binary tree in In-Order Traversal, my program will stop running.

void myCarSystem::remove(string m)
{
    //Locate the element
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    while(curr != NULL)
    {
         if(curr->Model.compare(m) == 0)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(m.compare(curr->Model) > 0)
                curr = curr->right;
             else
                curr = curr->left;
         }
    }
    if(!found)
		 {
        cout<<" Data not found! "<<endl;
        return;
    }

    // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else // left child present, no right child
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }

		 //We're looking at a leaf node
		 if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
		 		 delete curr;
		 		 return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }

                curr->Model = lcurr->Model;

                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->Model = tmp->Model;
               curr->right = tmp->right;
               delete tmp;
           }

        }
		 return;
    }

}

Please give some guild to me. Thank you.
Cjjack88

[Tom Gunn]

When i remove the root of the binary tree and I view the binary tree in In-Order Traversal, my program will stop running.

Then you are not resetting the links the way they should be. Removing the root means replacing the root with either the inorder predecessor or successor. Something like this:

Original:
    D
 B     F
A C   E G

Delete the root:
    *
 B     F
A C   E G

Make the inorder predecessor the root:
    C
 B     F
A *   E G

Delete the inorder predecessor:
    C
 B     F
A     E G

That behavior should fall out of your deletion algorithm because it is the same as the two child case for any node. But you also need to reset the root pointer. In the example above, if root still points to D after the algorithm finishes, the tree will be broken. So at the end, the address of C should be assigned to root to finish things up, but only if it was D that was deleted. That is an easy test because parent will be NULL if the root has a matching value.

[cjjack88]

Thank you for reply, i need some time to understand it. If i just have 3 data in the tree, eg: 1, 2 and 3, and i remove 1 in thee, should 3 become the new root in this tree?

[Tom Gunn]

If i just have 3 data in the tree, eg: 1, 2 and 3, and i remove 1 in thee, should 3 become the new root in this tree?

If 1 is the root, then either 2 or 3 could be the new root. You can pick whether the inorder predecessor or successor becomes the new root. But it is not as easy as just making the root's immediate left or right child the new root because you still have to maintain the binary search invariant that an inorder traversal produces a sequence that is sorted in ascending order.

[cjjack88]

ok, I try to code it 1st....
Thank you..

[desire_963]

thankssssssssssss alottttttt

[troyduff281]

pardon me...what do u mean by, chkr, lcurrp, tmp, curr and lcurr in your program. I am a newbie in programming. But I am willing to know about it.