Binary Search Tree Clear Method Malloc Error

[kingkush]

I'm attempting to clear my entire binary search tree but it gives me a malloc error after deleting the first node. I've looked online at multiple examples and even in my book but it doesnt seem to work. Any ideas whats going wrong?

Clear function:

void Tree::clear(Node* r)
{
    if(!r)
    {
        std::cout << "Not root" << std::endl;
        return;
    }
    else
    {
        if(r->left)
        {
            clear(r->left);
        }
        if(r->right)
        {
            clear(r->right);
        }
        if(r == nullptr)
        {
            return;
        }
        std::cout << "Delete: " << r->name << std::endl;
        delete r;
    }
}

[Chervil]

Well, I just dropped that function into my version of the complete program. It seemed to work ok, the messages appeared as expected.

Perhaps there's something about the way you are calling the function in another part of the program?

[kingkush]

I use a public function to call this private function. The public function only calls the private version passing in the root.

It says pointer being freed was not allocated. There was no error when you ran the code?

I just realized I would clear the BST once and once the program ended I believe the destructor was trying to delete the nodes which were already deleted. However if I clear the tree and try to insert i get the error again. Any ideas?

Firgured it out. I did not finish the remove function and i was calling it before in main and it was causing issues. Thank you for letting me know it worked properly though! It helped me debug my code better!

[Chervil]

Firgured it out.

That's good.

I didn't want to distract you from solving the issues with your own code before, so I didn't post this earlier. It's a version of your own code, just tweaked here and there to use constructors and destructors.

#include <iostream>
#include <string>

class Node {
public:
    Node() : right(nullptr), left(nullptr) { }
    Node(std::string n, std::string p) : 
        name(n), phone(p), right(nullptr), left(nullptr) { }
    
    ~Node()
    {
        std::cout << "Deleting: " << name << ", " << phone << '\n';
        delete left;
        delete right;
    }
    
    friend class Tree;

private:
    std::string name;
    std::string phone;
    Node * right;
    Node * left;
};

class Tree {

public:
    Tree() : root(nullptr) { }
    ~Tree()
    {
        delete root;
    }

    int insert(std::string n, std::string p);
    
    std::string find(std::string n) const
    {
        return find(root, n);
    }

private:

    Node * root;

    void insert(Node*& r, std::string n, std::string p);
    std::string find(Node*r, std::string n) const;

};

int Tree::insert(std::string n, std::string p)
{
    insert(root, n, p);

    // Return something once figured out it works correctly

    return 0;
}

void Tree::insert(Node*& r, std::string n, std::string p)
{
    if (r == nullptr)
    {
        r = new Node(n,p);
    }
    else if(n > r->name)
    {
        insert(r->right, n, p);
    }
    else
    {
        insert(r->left, n, p);
    }

}

std::string Tree::find(Node*r, std::string n) const
{
    if (root == nullptr)
    {
        std::cout << "No Tree" << std::endl;
        return " ";
    }

    if (r == nullptr)
    {
        return " ";
    }
    else if (r->name == n)
    {
        return r->phone;
    }
    else if (r->name < n)
    {
        return find(r->right, n);
    }
    else
    {
        return find(r->left, n);
    }
}


int main()
{
    Tree tree;

    tree.insert("fred", "123");
    std::string result = tree.find("fred");
    std::cout << "1 result = " << result << '\n';


    tree.insert("joe", "456");

    result = tree.find("fred");
    std::cout << "2 result = " << result << '\n';

    result = tree.find("joe");
    std::cout << "3 result = " << result << '\n';

    tree.insert("Suzy Smythe", "789");
    tree.insert("Daphne Bentwater", "5356");
    tree.insert("Mildred Murfin", "47634");
    tree.insert("Richard Lamb", "65676");

    result = tree.find("Daphne Bentwater");
    std::cout << "4 result = " << result << '\n';

    std::cout << "Done\n";
}

One thing it doesn't have is a clear() function. Probably it would look like this (but not tested):

void Tree::clear()
{
    delete root;
    root = nullptr;
}