Binary Tree In Order Traversal causing Stack Overflow

Question

Ok so, I have a read method that is reading the values in correctly (all 7000), (hand written 15 values as a tree structure), doesn't create any errors.

However, when it comes to the output of the binary tree I am using the method as stated on several websites.

The error I am getting is a stack overflow, and I am assuming its due to the recursive calls and never breaking out, But I have no idea why this isn't working.

Any help is appreciated, thanks.

Code Listed Below:

// Read
void BinaryTreeStorage::read(ifstream& _fin)
{
        // Get first line with number of names in it
        string numberOfNamesString;
        getline(_fin, numberOfNamesString);

        // Loop through all the names
        string line;
        int num = 0;
        while (!_fin.eof())
        {
                getline(_fin, line);
                if (line != "")
                {
                        // Insert Value Here
                        if (root != NULL)
                        {
                                insert(line, root);
                        }
                        else
                        {
                                insert(line);
                        }
                }
        }
}

// Write
void BinaryTreeStorage::write(ofstream& _out) const
{
        inorderPrint(_out, root);
}

// inorderPrint
void BinaryTreeStorage::inorderPrint(ofstream& _out, node *_root) const
{
        if (_root != NULL)
        {
                // Inorder
                inorderPrint(_out, root->left);
                _out << root->nodeValue;
                cout << root->nodeValue << " ";
                inorderPrint(_out, root->right);
        }
}

// Insert if root is null
void BinaryTreeStorage::insert(string _nodeValueIn)
{
    if(root!=NULL)
        insert(_nodeValueIn, root);
    else
    {
        root=new node;
        root->nodeValue=_nodeValueIn;
        root->left=NULL;
        root->right=NULL;
    }
}

// Insert when root is not null
void BinaryTreeStorage::insert(string _nodeValueIn, node *leaf)
{
    if(_nodeValueIn< leaf->nodeValue)
    {
        if(leaf->left!=NULL)
            insert(_nodeValueIn, leaf->left);
        else
        {
            leaf->left=new node;
            leaf->left->nodeValue=_nodeValueIn;
            leaf->left->left=NULL;    //Sets the left child of the child node to null
            leaf->left->right=NULL;   //Sets the right child of the child node to null
        }  
  }
  else if(_nodeValueIn>=leaf->nodeValue)
  {
        if(leaf->right!=NULL)
            insert(_nodeValueIn, leaf->right);
        else
        {
            leaf->right=new node;
            leaf->right->nodeValue=_nodeValueIn;
            leaf->right->left=NULL;  //Sets the left child of the child node to null
            leaf->right->right=NULL; //Sets the right child of the child node to null
        }
    }
}

Welcome to Stack Overflow! Asking strangers to spot errors in your code by inspection is not productive. You should identify (or at least isolate) the problem by using a debugger or print statements, and then come back with a more specific question (once you've narrowed it down to a 10-line test-case). — Oliver Charlesworth
– Oliver Charlesworth, Commented Apr 30, 2012 at 20:17
in the last function, insert, a lot of it doesn't make sense. I can see a lot of potential for infinite recursion. However I'm not tracing the whole thing, that's what a debugger is for. Also, you should use string.empty() to check if an std::string is empty — std''OrgnlDave
– std''OrgnlDave, Commented Apr 30, 2012 at 21:05

comonad · Accepted Answer · 2012-04-30 21:26:11Z

2

You have a bug in BinaryTreeStorage::inorderPrint, your param _root is not used where intended: You always loop on root instead.

hint: Avoid using similar names!

hint: Avoid using std to avoid bugs, unless you write std:: too often in nested templates.

hint: Do not use _ at the beginning or end of names.

hint: Do not compare with NULL: Write if(n) instead of if(n!=NULL).

hint: Do not nest blocks when not needed:

void BinaryTreeStorage::inorderPrint(std::ofstream& out, node *n) const
{
    if(!n) return;

    inorderPrint(out, n->left);
    out << n->nodeValue; // no separator??
    std::cout << n->nodeValue << " ";
    inorderPrint(out, n->right);
}

answered Apr 30, 2012 at 21:26

comonad

5,3092 gold badges36 silver badges32 bronze badges

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

Comments

deebee · Accepted Answer · 2012-04-30 20:58:25Z

1

void BinaryTreeStorage::inorderPrint(ofstream& _out, node *_root) const
{
        if (_root != NULL)
        {
                // Inorder
                inorderPrint(_out, root->left);

In the above code, I can see _root defined but you're using root in your call (last line above). I think that is causing the infinite loop.

edited Apr 30, 2012 at 20:58

answered Apr 30, 2012 at 20:42

deebee

1,74713 silver badges14 bronze badges

Comments

John Percival Hackworth · Accepted Answer · 2012-04-30 20:18:29Z

0

When you constructed your tree nodes did you ensure that the left and right pointers are initialized to NULL?

answered Apr 30, 2012 at 20:18

John Percival Hackworth

11.5k2 gold badges31 silver badges38 bronze badges

2 Comments

MitchellT Over a year ago

Yes, the left and right are set to NULL Updated Code accordingly.

John Percival Hackworth Over a year ago

Then walk through your insert logic by hand.

Derek Ledbetter · Accepted Answer · 2012-04-30 20:50:24Z

0

The depth of the call tree of inorderPrint is the same as the depth of the tree itself. It looks like you don't try to keep the tree balanced, so the depth can get as large as the size of the tree.

There are a few ways of fixing this. You can make sure that the tree always remains balanced so that the depth grows logarithmically with the size of the tree. Or you can make the tree threaded, which lets you visit the nodes iteratively.

answered Apr 30, 2012 at 20:50

Derek Ledbetter

4,9054 gold badges23 silver badges18 bronze badges

Collectives™ on Stack Overflow

Binary Tree In Order Traversal causing Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related