Remove everything from binary tree

[Jaily]

Can I somehow use the following code to remove all the elements of a binary tree?

void BinarySearchTree::remove(int d)
{
    //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->data == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(d>curr->data) 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->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->data = tmp->data;
		curr->right = tmp->right;
               delete tmp;
           }
        }
		 return;
    }
}

(Found here )

I'm inserting 10 random integers first and then want to remove all of them. But with the code above I have to choose a number to look for and remove in the tree. Ideas?

[alwaysLearning0]

Hi,

No, it will delete only one Node with a certain value.

You can delete binary tree in so many different ways.

First try to do traversing,

Inorder, preorder, postorder.

Once you understand traversing, then you can delete whatever way you like.

simplest way to delete will be, delete root, and adjust your tree.

in the above program, from main (or from some other function) check if root is null or not, if root is not null then call your remove function with the found integer in the root.

keep calling until root is not null.

I hope it helps.

[Jaily]

Hi,

No, it will delete only one Node with a certain value.

You can delete binary tree in so many different ways.

First try to do traversing,

Inorder, preorder, postorder.

Once you understand traversing, then you can delete whatever way you like.

simplest way to delete will be, delete root, and adjust your tree.

in the above program, from main (or from some other function) check if root is null or not, if root is not null then call your remove function with the found integer in the root.

keep calling until root is not null.

I hope it helps.

Hmmm.. Okey. Thank you for the help.

In my binary tree program I'm already doing inorder traversing. I'll try to work out a solution like you described!

[nbaztec]

The best way is to call a post order traversal.
Left->Right->Root

void DeleteAll(Node *myNode)
{
  DeleteAll(myNode->LeftChild);
  DeleteAll(myNode->RightChild);
  delete myNode;
}

The above function is really post-order traversing but instead of just displaying we are deleting the value as well.