binary search tree implementation

[cppnoob25]

I've been practicing binary search trees and for the insert function I did this.

I keep reading about recursion with trees but I don't really understand it. So how would I achieve this recursively?

Edit: I have posted my recursive attempt below and would like feedback on it. It is the 4th post. Thanks.

class Btree{

public:

    Btree();
    void insert(int x);
    void remove(int value);
    void print();


private:

    struct Node{
        int data;
        Node * left;
        Node * right;
    };

    Node * root;

};

Btree::Btree()
{
    root = NULL;
}

void Btree::insert(int x)
{
    Node * n = new Node;
    Node * current;
    Node * temp;

    n->data = x;
    n->left = NULL;
    n->right = NULL;

    if(root == 0)
    {
        root = n;
        n->right = NULL;
        n->left = NULL;
    }
    else{
        current = root;
        while(current != NULL)
        {
            temp = current;
            if(current->data > n->data)
            {
                current = current->left;
            }
            else{
                current = current->right;
            }
        }

        if(n->data < current->data)
        {
            temp->left = n;
        }
        else{
            temp->right = n;
        }
    }
}

[poteto]

The tree works right?
I don't have any experience with pointer lists, so take some salt. Note, I'm taking this as if you have to do this in one function.

Firstly, I think you need to change the function a bit:

//this is inside the class, remove the initialization for the one outside.
template<int x>
void insert(Node * n = new Node{x,NULL,NULL}, Node * current = root, Node * temp = NULL);

(obviously remove the initialization inside the function)

Then remove the current = root, change the while statement to be an if statement, and at the end of it, call the function with the right values.

And that's it.

[cppnoob25]

Actually I think that sends me in the right direction. I'll take a crack at it until I get it. Thanks

[cppnoob25]

This is my attempt. Does this recursive insert work correctly? I just want to make sure I'm going in the right direction.

class Btree{

private:

    struct Node{
        int data;
        Node * left;
        Node * right;
    };

    Node * root;

public:

    Btree();
    ~Btree();
    void insert(int x);
    void insert(Node * root, int x);
    void remove(int value);
    void print();
};

Btree::Btree()
{
    root = NULL;
}

void Btree::insert(Node * topNode,int x)
{
    Node * temp = topNode;

    if(temp == NULL)
    {
        Node * n = new Node;
        n->left = 0;
        n->right = 0;
        n->data = x;
        temp = n;
    }
    else{
        if(x < temp->data)
        {
            insert(temp->left, x);
        }
        else{
            insert(temp->right, x);
        }
    }
}


void Btree::insert(int x)
{
    insert(root, x);
}

/*
void Btree::insert(int x)
{
    Node * n = new Node;
    Node * current;
    Node * temp;

    n->data = x;
    n->left = NULL;
    n->right = NULL;

    if(root == 0)
    {
        root = n;
        n->right = NULL;
        n->left = NULL;
    }
    else{
        current = root;
        while(current != NULL)
        {
            temp = current;
            if(current->data > n->data)
            {
                current = current->left;
            }
            else{
                current = current->right;
            }
        }

        if(n->data < current->data)
        {
            temp->left = n;
        }
        else{
            temp->right = n;
        }
    }
}
*/

The iterative version is commented out here.

[ne555]

> void Btree::insert(Node * topNode,int x)
read about passing arguments by value and by reference.
any change may to `topNode' inside the `insert()' function would not be visible from outside. That means that you never insert anything, you are just leaking memory

[cppnoob25]

How else should I do this?

void Btree::insert(Node & topNode ,int x)

Something along those lines?