Execution of binary search tree on g++ goes into infinite loop

Question

I have written this BST to count the number of each words in a given file. The file has repeated words in every line.

/*all necessary headers*/
class tree
{
public:
    tree(string _word) : left( NULL ), right ( NULL ), m_word(_word), count(1) {}

    tree* createTree(tree *newNode, string _word)
    {

        if( newNode == NULL )
            newNode = new tree(_word);

        else if( _word == newNode->m_word)
            newNode->count++;

        else if( _word < m_word)
            newNode->left  = createTree(newNode->left,_word);

        else
            newNode->right = createTree(newNode->right,_word);

        return newNode;
    }

private:
    string m_word;
    int count;
    tree *left;
    tree *right;

};

int main()
{
    string csword;
    tree *node = NULL;
    ifstream str("word.txt");
    while( !str.eof())
    {
        str>>csword;
        node = node->createTree(node,csword);

    }
}

My queries are : 1. In main() i am initializing the node to NULL, and I am using the same pointer to call the trees methods. Shouldn't the program crash? Since i am de-referencing a NULL pointer?

2 : when I run this piece of code on a g++ compiler( gcc 4.6.3 ), the program hands in the createTree() method when _word == newNode->m_word and does not come back. There seems to be an infinite loop going on in the else if ( _word == newNode->m_word ) condition.

But executing the same code on Visual Studio 2008 has no issues and i am able to get correct answer.

Any idea about the query 1 and 2 ?

Side Note: Change `while( !str.eof())` to `while(str >> csword)` and **remove** the extraction inside the while-loop. [See this question](http://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-considered-wrong) for details concerning *why*. — WhozCraig, Aug 27 '13 at 05:54

Karthik T · Answer 1 · 2013-08-27T06:03:04.080

2

Depending on implementation (mine was MSVC++), it might cause segmentation fault only if you actually access any of the members of the non-existant object. Since your createTree does not touch anything, it works almost like a static function, it does not cause a segmentation fault.

Perhaps you should make it static, makes more sense than the way it is right now.

edited Aug 27 '13 at 06:03

answered Aug 27 '13 at 05:54

Karthik T

31,456
5
68
87

It could cause a segmentation fault anyway. It is undefined behaviour. – juanchopanza Aug 27 '13 at 05:59
@juanchopanza that is what I noticed on MS VC++, ill add the disclaimer – Karthik T Aug 27 '13 at 06:02
@juanchopanza I asked that question in [C++ chat a few days ago](http://chat.stackoverflow.com/transcript/34546?m=11424599#11424599). Does the standard actually call it out as undefined behavior to fire a class-static method from an indeterminate or nullptr object ptr of said class? If so, is there a specific section I can peek at? I searched in vain, but it wouldn't be the first time i missed something in that thing. – WhozCraig Aug 27 '13 at 06:04
@WhozCraig I am pretty sure dereferencing a null pointer is UB, but I don't have the quote to back it up right now. Note the method being called is not `static`. – juanchopanza Aug 27 '13 at 06:06
1

There is on what standard says about dereferencing NULL pointer - http://stackoverflow.com/questions/2474018/when-does-invoking-a-member-function-on-a-null-instance-result-in-undefined-beha – SChepurin Aug 27 '13 at 07:05
What about the second question? Any ideas on that?? – Kartikkumar Rao Aug 27 '13 at 14:44
@karthikkumar24 I am afraid not, it seems fine to my eyes.. Perhaps you can try a debugger – Karthik T Aug 28 '13 at 00:53
@KarthikT I was thinking there was some compiler optimization involved here. – Kartikkumar Rao Aug 28 '13 at 04:33

Execution of binary search tree on g++ goes into infinite loop

1 Answers1