Deleting from binary tree

[pepepe]

Learning how to delete a node from a binary tree in three cases by myself -- leaf, one child, two child. When I run it, it gives error: 'deleteNode' was not declared in this scope'.

Btw is this the right approach?

[jonnin]

it seems like deletenode etc should be members of your classes, not free floating functions. ??

that aside,
I think deletenode is having woes because of the template. Remember that templates let the compiler generate a concrete version of the code for the type specified, but how does it know what to do here, when its argument is a template of unknown type?

I think you should fix the first part (tie these functions to the class) and that will resolve the template and solve the second problem, and its the right thing to do.

I am not great with templates, and I don't even know if its possible to free float a function this way with templates, and if it is, how to fix it. ?

[tpb]

You shouldn't use free to free memory allocated with new. Use delete instead.

#include <iostream>

template <typename T>
class Tree;

template <typename T>
class Node {
    T value;
    Node<T> *left, *right;
public:
    Node(T value) : value(value), left(nullptr), right(nullptr) {}
    T getvalue() { return value; }
    void print() {
        if (left) left->print();
        std::cout << value << ' ';
        if (right) right->print();
    }
    friend class Tree<T>;
};

template <typename T>
class Tree {
    Node<T> *root;
public:
    Tree() : root(nullptr) {}
    void print() { if (root) root->print(); std::cout << '\n'; }
    void add(T value);
    void remove(T value);
};

template <typename T>
void Tree<T>::add(T value) {
    Node<T> **nd = &root;
    while (*nd)
        if (value <= (*nd)->getvalue())
            nd = &(*nd)->left;
        else
            nd = &(*nd)->right;
    *nd = new Node<T>(value);
}

template <typename T>
void Tree<T>::remove(T value) {
    Node<T> **nd = &root;
    while (*nd) {
        if (value == (*nd)->getvalue()) {
            Node<T> *del = *nd;
            if (!del->left)
                *nd = del->right;
            else {
                Node<T> **farleft = &del->right;
                while (*farleft) farleft = &(*farleft)->left;
                *farleft = del->left->right;
                del->left->right = del->right;
                *nd = del->left;
            }
            delete del;
            break;
        }
        else if (value < (*nd)->getvalue())
            nd = &(*nd)->left;
        else
            nd = &(*nd)->right;
    }
}

int main() {
    Tree<int> t;
    for (int n: {6, 8, 5, 7, 1, 3, 9, 0, 2, 4}) t.add(n);
    t.print();
    for (int n: {3, 7, 1, 6, 4, 2, 9, 5, 0, 8}) {
        std::cout << "Removing: " << n << '\n';
        t.remove(n);
        t.print();
    }
}

[pepepe]

the debugger said there's an error in cout << "Level: " << level << " " << p->key << endl;.

it produced the following

Program received signal SIGSEGV, Segmentation fault.                        
0x00007ffff7b8de43 in std::basic_ostream<char, std::char_traits<char> >& std
::operator<< <char, std::char_traits<char>, std::allocator<char> >(std::basi
c_ostream<char, std::char_traits<char> >&, std::basic_string<char, std::char
_traits<char>, std::allocator<char> > const&) ()  

how do i fix this?

[Ganado]

I'm going to guess that it starts failing after you try to delete nodes.

            else if (p -> right == nullptr)
            {
              tempP = p;
              tempP = p-> left;
              delete tempP;
            }

What are you trying to do here, in English?
Say what each line is doing out loud to yourself (like, actually, say it out loud to yourself -- do it), along with the intended purpose of each line). And then tell us.

You aren't deleting p, that's for sure. You also aren't restructuring your tree after the deletion; the parent will be looking at junk data, as far as I can tell.

Questions to ask yourself:
* Why do you assign tempP a value, and then immediately re-assign it? That's a red flag right there.
* Why do check for p->right being nullptr, but then assume that p->left isn't a nullptr? Seems like a weird setup.

Also, for bug testing, try inserting data that isn't already ordered. That will help you hit the most conditional branches.

Most importantly, general advice: Start small.

Don't start with 10 items, and then try to figure out what went wrong from the wreckage. Start with 1 item. Maybe 2 items. And see if that works. If 1 or 2 items works, try to insert 3 items. If there is a problem, it will be much easier to track by hand when you are only dealing with a few items.

[TheIdeasMan]

Just to reinforce Ganado's comment about the ordered data: Do you realise what that looks like in a BST? Each Node has 1 child, like this:

A
\
B
\
C
\
D

[pepepe]

Thanks for the comment. I corrected the code so that it would properly reattach the left child.

The debugger produces Program received signal SIGSEGV, Segmentation fault.
at line 30 cout << "Level: " << level << " " << p->key << endl

managed to corrected the error! p had to be a reference. Ty for help all.