C++ Binary Search Tree and Pointers

Question

could you please tell me why the call of the method binaryTree.Exists(5); says that "5 doesn't exist in the binary tree"? when debugging, it's like when trying to access the node where 5 is inserted doesn't exist anymore. i don't see why. thank you!!!

#include <iostream>

using namespace std;


class Node
{
    private:
        int _value;
        Node* left;
        Node* right;

    public:
        Node(int value):_value(value), left(NULL), right(NULL)
        {
        }
        Node* returnLeftChild()
        {
            return left;
        }
        Node* returnRightChild()
        {
            return right;
        }
        void setLeftChild(Node* l)
        {
            left=l;
        }
        void setRightChild(Node* r)
        {
            right=r;
        }
        int getValue()
        {
            return _value;
        }
};

class BinaryTree
{
    private:
        Node parent;
        void AddToOneTree(Node* parent, int value)
        {
            if (value==parent->getValue())
            {
                return;
            }
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()==NULL)
                {
                    Node newNode(value);
                    parent->setRightChild(&newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnRightChild(), value);
                }
            }
            if (value<parent->getValue())
            {
                if (parent->returnLeftChild()==NULL)
                {
                    Node newNode(value);
                    parent->setLeftChild(&newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnLeftChild(), value);
                }
            }           
        }

        void LookForValue(Node* parent, int value, bool found)
        {
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()!=NULL)
                {
                    if (parent->returnRightChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnRightChild(), value, found);
                    }
                }
            }
            else if (value<parent->getValue())
            {
                if (parent->returnLeftChild()!=NULL)
                {
                    if (parent->returnLeftChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnLeftChild(), value, found);
                    }
                }
            }
            HERE:;
        }

    public:
        BinaryTree(int parentValue):parent(parentValue)
        {   
        }

        void Add(int value)
        {
            AddToOneTree(&parent, value);
        }

        void Exists(int value)
        {
            bool found = false;
            if (parent.getValue()==value)
            {
                cout << value << " exists in the Binary Tree." << endl;
            }
            else{
                LookForValue(&parent, value, found);
                if (found)
                {
                    cout << value << " exists in the Binary Tree." << endl;
                }else
                {
                    cout << value << " doesn't exist in the Binary Tree." << endl;
                }
            }
        }

};

int main()
{
    BinaryTree binaryTree(9);
    binaryTree.Add(5);
    binaryTree.Add(5);

    binaryTree.Exists(9);
    binaryTree.Exists(5);
}

Vlad from Moscow · Accepted Answer · 2015-10-29 09:41:42Z

1

At least function AddToOneTree is wrong and is the reason of undefined behaviour of the program

For example in this code block

if (parent->returnRightChild()==NULL)
{
    Node newNode(value);
    parent->setRightChild(&newNode);
    return;
}

you create a local variable newNode and its address asign to the pointer of right child. However as the variable is local it is destroyed after the control leaves the code block and the corresponding pointer in the tree will be invalid.

You need to dynamically allocate nodes and add them to the tree.

A better design is when the class BinaryTree contains a ponter to the head of the tree. Declare data member parent like

class BinaryTree
{
    private:
        Node *parent;
             ^^^^^^^^
    //...

and correspondingly rewrite the class.:)

edited Oct 29, 2015 at 9:41

answered Oct 29, 2015 at 9:36

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

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

3 Comments

LBes Over a year ago

Did not see the undefined behaviour, upvote deserved. I bet that this answer should be the accepted one

Vlad from Moscow Over a year ago

@LBesancon Thanks. You are a kind person.:)

LBes Over a year ago

It's not kindness. Among all the problems that others (and I) reported, this is probably the biggest one and we failed to notice it so this definitely should be the accepted answer. OP should have spent more time reading answers instead of jumping to the first one that may solve momentarily the problem but still fails to grasps the undefined behaviour

Danil Prokhorenko · Accepted Answer · 2015-10-29 09:27:44Z

0

You should replace this string:

void LookForValue(Node* parent, int value, bool found)

to this:

void LookForValue(Node* parent, int value, bool &found)

or just set return value to bool in LookForValue function and write something like this:

found = LookForValue(&parent, value, found);

answered Oct 29, 2015 at 9:27

Danil Prokhorenko

1,1041 gold badge11 silver badges28 bronze badges

Comments

JNK · Accepted Answer · 2015-10-29 09:39:40Z

0

void LookForValue(Node* parent, int value, bool found)

You are passing found by value. That means the value will be copied. When you change found inside of the method LookForValue you are only changing this copy.

void LookForValue(Node* parent, int value, bool& found)

This will pass found by reference, so if you change it inside of LookForValue the original in the Exists method will be changed as well.

You can also just return a bool value like this:

bool LookForValue(Node* parent, int value, bool &found)

And then just write return true; instead of

found= true;
goto HERE;

That way you also get rid of the goto.

answered Oct 29, 2015 at 9:39

JNK

8367 silver badges13 bronze badges

Comments

LBes · Accepted Answer · 2015-10-29 09:42:50Z

You have several issues in your code.

The first one is that the boolean found is never returned by the LookForValue function. You can either change bool found to bool & found so that you do not have to return anything or change the return type of LookForValue to bool in which case you'll need to change your code to something like this:

bool LookForValue(Node* parent, int value, bool found)
{
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()!=NULL)
                {
                    if (parent->returnRightChild()->getValue()==value)
                    {
                        return true ;
                    }
                    else
                    {
                        LookForValue(parent->returnRightChild(), value, found);
                    }
                }
            }
            else if (value<parent->getValue())
            {
                if (parent->returnLeftChild()!=NULL)
                {
                    if (parent->returnLeftChild()->getValue()==value)
                    {
                        return true ;
                    }
                    else
                    {
                        LookForValue(parent->returnLeftChild(), value, found);
                    }
                }
            }
}

If you change the return type please also think about changing one line in your Exists function just after the else:

found = LookForValue(&parent, value, found);

I haven't tested the code yet so there might be other issues still.

The next time you face such an issue, I suggest trying to use gdb as it will probably help in detecting what your code is really doing so that you can figure out what may be wrong. For instance here, you could have seen that the found was never set to true in your Exists function just by "printing" step by step the value of your found variable.

Also, I think the way you designed your classes is not really good. Parent should be a pointer, pointing to the root of the tree. I would suggest a complete re-designing of your code. You can find some good implementations online that you can be your code upon.

Finally the goto is definitely a bad idea... I would get rid of that too.

Here is a link: en.wikipedia.org/wiki/GNU_Debugger. You might also want to change the design of your code

Dave ddd · Accepted Answer · 2015-10-29 10:00:10Z

thanks for everyone. i've changed passing found by reference and allocated memeory using "new" for new nods.This now works!!

#include <iostream>

using namespace std;


class Node
{
    private:
        int _value;
        Node* left;
        Node* right;

    public:
        Node(int value):_value(value), left(NULL), right(NULL)
        {
        }
        Node* returnLeftChild()
        {
            return left;
        }
        Node* returnRightChild()
        {
            return right;
        }
        void setLeftChild(Node* l)
        {
            left=l;
        }
        void setRightChild(Node* r)
        {
            right=r;
        }
        int getValue()
        {
            return _value;
        }
};

class BinaryTree
{
    private:
        Node parent;
        void AddToOneTree(Node* parent, int value)
        {
            if (value==parent->getValue())
            {
                return;
            }
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()==NULL)
                {
                    Node* newNode=new Node(value);
                    parent->setRightChild(newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnRightChild(), value);
                }
            }
            if (value<parent->getValue())
            {
                if (parent->returnLeftChild()==NULL)
                {
                    Node* newNode=new Node(value);
                    parent->setLeftChild(newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnLeftChild(), value);
                }
            }           
        }


        void LookForValue(Node* parent, int value, bool &found)
        {
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()!=NULL)
                {
                    if (parent->returnRightChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnRightChild(), value, found);
                    }
                }
            }
            else if (value<parent->getValue())
            {
                if (parent->returnLeftChild()!=NULL)
                {
                    if (parent->returnLeftChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnLeftChild(), value, found);
                    }
                }
            }
            HERE:;
        }

    public:
        BinaryTree(int parentValue):parent(parentValue)
        {   
        }

        void Add(int value)
        {
            AddToOneTree(&parent, value);
        }

            void Exists(int value)
        {
            bool found = false;
            if (parent.getValue()==value)
            {
                cout << value << " exists in the Binary Tree." << endl;
            }
            else{
                LookForValue(&parent, value, found);
                if (found)
                {
                    cout << value << " exists in the Binary Tree." << endl;
                }else
                {
                    cout << value << " doesn't exist in the Binary Tree." << endl;
                }
            }
        }

};

int main()
{
    BinaryTree binaryTree(9);
    binaryTree.Add(5);
    binaryTree.Add(6);
    binaryTree.Add(1);
    binaryTree.Add(15);
    binaryTree.Add(13);
    binaryTree.Add(2);
    binaryTree.Add(2);
    binaryTree.Add(0);
    binaryTree.Add(4);

    binaryTree.Exists(9);
    binaryTree.Exists(5);
    binaryTree.Exists(6);
    binaryTree.Exists(1);
    binaryTree.Exists(15);
    binaryTree.Exists(13);
    binaryTree.Exists(2);
    binaryTree.Exists(2);
    binaryTree.Exists(0);
    binaryTree.Exists(4);
    binaryTree.Exists(11);

    binaryTree.Exists(412);

    binaryTree.Exists(40);


}

Still some issues with your code, see my post for explanations ;). Glad that it works nonetheless :). And usually, after accepting an answer, OP should not post is whole code as an answer too ;)

Collectives™ on Stack Overflow

C++ Binary Search Tree and Pointers

5 Answers 5

3 Comments

Comments

Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

Comments

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related