Can't find pointer error with my Binary Search Tree implementation?

Question

I am new to C++ and I can't find why the root of the tree changes whenever I add anything to the tree. It must be a pointer problem but I can't figure it out. For example:

BST bst;
bst.insert(5);
bst.insert(2);

I get the correct output when I insert 5, but when I insert 2 it says:

Inserted 2 to the left of 2.

Node class:

class Node
{
// Let BST directly access members.
friend class BST;
public:
    // Constructor
    Node(int i);
    int getValue();
protected:
    int value;
    Node *left;
    Node *right;
};

// Constructor
Node::Node(int i)
{
    value = i;
    left = 0;
    right = 0;
}

int Node::getValue()
{
 return value;
}

BST class:

class BST
{
    public:
        BST();
        void insert(int i);
        void print();
        void print(Node *n);
    private:
        // root of the tree
        Node *root;
};

BST::BST()
{
    root = 0;
}

void BST::insert(int i)
{
    Node *cur = this->root;
    Node *prev;
    Node new_node(i);
    if(cur == 0)
    {
        this->root = &new_node;
        cout << "Root is empty, insert " << this->root->value << " as root." << endl;
        return;
    }
    while(cur != 0)
    {
        prev = cur;
        if(i <= cur->value)
        {
            cur = cur->left;
            if(cur == 0)
            {
                prev->left = &new_node;
                cout << "Inserted " << prev->left->value << " to the left of " << prev->value << endl;
                return;
            }
        }
        else if(i > cur->value)
        {
            cur = cur->right;
            if(cur == 0)
            {
                prev->right = &new_node;
                cout << "Inserted " << prev->right->value << " to the right     of " << prev->value << endl;
                return;
            }
        }
    }
}

void BST::print()
{
    print(this->root);
}

void BST::print(Node *n)
{
    if(n == 0)
    {
        return;
    }
    print(n->left);
    cout << n->value << " " << endl;
    print(n->right);
}

Thanks.

Have you stepped through line by line during execution using a debugger? — Cory Kramer
– Cory Kramer, Commented Nov 30, 2015 at 12:49
It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: How to debug small programs — NathanOliver
– NathanOliver, Commented Nov 30, 2015 at 12:49
Have you noticed that you are not allocating your nodes? You create them by value inside insert method and they are deleted as soon as your code exit it. It might be unrelated to your issue but it will bite you anyway later on. — Mateusz Kubuszok
– Mateusz Kubuszok, Commented Nov 30, 2015 at 12:50
@maddening: I reckon that's precisely the problem. The symptoms fit. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Nov 30, 2015 at 12:53
@maddening Ah right so I didn't even create my nodes correctly... I thought Node new_node(i) was enough in C++ to create the object. Thanks. — Neurion
– Neurion, Commented Nov 30, 2015 at 12:59

Ivaylo Strandjev · Accepted Answer · 2015-11-30 12:50:47Z

4

Node new_node(i); this creates a local variable. Later you assign its address to root. Note that using the data written at the address of a local variable outside of its scope will invoke undefined behavior. You need to allocate dynamic memory and later take care to deallocate it.

answered Nov 30, 2015 at 12:50

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lightness Races in Orbit Over a year ago

Yes, this. The addresses in the tree are likely all the same, hence the "replacing value" behaviour the OP has seen when [undefinedly] dereferencing them.

JSF · Accepted Answer · 2015-11-30 12:50:31Z

1

You are storing the address of a local object:

Node new_node(i);

...

this->root = &new_node;

When the local object goes out of scope, further use of that address is undefined behavior.

You wanted:

   Node* new_node = new Node(i);

...

   this->root = new_node;

etc.

answered Nov 30, 2015 at 12:50

JSF

5,3211 gold badge15 silver badges21 bronze badges

7 Comments

Neurion Over a year ago

Thanks for that. I was trying to just create a node and then point root to that without having to create another pointer. Is there a way I can do it this way? Thanks.

Lightness Races in Orbit Over a year ago

@BelegNeurion: No, you need to "create another pointer". How can you have multiple, different pointers in your tree without "creating another pointer"? It's like asking how to have ten cars but only actually purchase one. At the moment you're renting one car ten times, and giving it back to the rental agency before you've even driven it once let alone ten times. :)

Konrad Rudolph Over a year ago

Please stop recommending new T to people. It’s 2015.

JSF Over a year ago

@KonradRudolph If there is supposed to be some insight hidden in that comment, you'll need some link or explanation.

Konrad Rudolph Over a year ago

@JSF I would have hoped that it was self-explanatory: don’t use new in your code, it’s bad. Use an appropriate smart pointer with a builder function (e.g. make_unique) or some other memory management construct. There’s rarely a good reason for using new at all any more, and certainly not here.

|

Collectives™ on Stack Overflow

Can't find pointer error with my Binary Search Tree implementation?

2 Answers 2

1 Comment

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related