Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

Alright, I've been debugging this for a few hours now and am getting nowhere. I'm trying to test a straightforward recursion-using binary tree.

When tested, I get a stack overflow at the third call in main's print_attributes function (noted below). A quick inspection of the callstack shows that it's full of hundreds of calls to binTree's binTree's height(Node < T >* node) (also noted below). When I "go-to" the call from the Call Stack, it takes me to size(Node < T >* node)'s call of leftside = size(node->left) (also noted below). I don't know what that's supposed to indicate, because neither of these functions call each other.

Here's an image of what the compiler says right as the stack overflow occurs (I'm using VS2013): http://puu.sh/ca3ti/e00f653282.png

Then here's an image of the compiler, after breaking, and clicking any of the height() calls in the call stack: http://puu.sh/ca2Qz/d35348ccce.png

Considering that it (appears to be) inserting nodes into the tree fine just before while using bintree's height()and/or size() function, I have no idea why the same function begins having issues here. I'm sorry for not being able to be able to more clearly explain what the issue is. I've been coding for a few years but I'm really lost with this. I've tried to provide as much information as I possibly could. Thank you so much to anyone who takes the time to help with this.

Node Class:

#include "340.h"

#ifndef H_NODE
#define H_NODE

// definition for class of nodes in bin tree

template < class T > class binTree; // forward declaration

template < class T >
class Node {
friend class binTree < T >;         // binTree is friend
public:
    // default constructor
    Node ( const T& x = T ( ), Node < T >* l = 0, Node < T >* r = 0 ) :
        data ( x ), left ( l ), right ( r ) { }
private:
    T data;                         // data component
    Node < T > *left, *right;       // left and right links
};
#endif

NodeTree Class:

#include "Node.h"

#ifndef H_TREE
#define H_TREE

template < class T > class binTree {
public:
    binTree(Node < T >* emptyroot = nullptr) : // default constructor
        root(emptyroot) { }

    bool empty() const // checks if tree empty
    {
        if (root == 0)
            return true;
        else
            return false;
    }

    unsigned size() const // returns no of nodes
    {
        if (root == 0)
            return 0;
        else
            return size(root);
    }

    unsigned height() const // returns height of tree
    {
        if (root == 0)
            return 0;
        else
            return height(root);
    }

    virtual void insert(const T& t) // inserts a node in shortest subtree
    {
        if (empty())
        {
            Node< T >* n = new Node< T >;
            n->data = t;
            root = n;
        }
        else
            insert(root, t);
    }
protected:
    Node < T >* root; // root of tree
private:
    unsigned size(Node < T >* node) const // private version of size ( )
    {
        unsigned leftside;
        unsigned rightside;

        if (node->left == 0)
            leftside = 0;
        else
            leftside = size(node->left); //******issue(?) here******

        if (node->right == 0)
            rightside = 0;
        else
            rightside = size(node->right);

        return(leftside + rightside + 1);
    }

    unsigned height(Node < T >* node) const // private version of height ( ) 
//*****issue(?) here************
    {
        unsigned leftside;
        unsigned rightside;

        if (node->left == 0)
            leftside = 0;
        else
            leftside = height(node->left);

        if (node->right == 0)
            rightside = 0;
        else
            rightside = height(node->right);

        return 1 + max(leftside, rightside);
    }

    void insert(Node < T >* node, const T& t) // private version of insert ( )
    {
        if (node->left == 0)
        {
            Node< T >* n = new Node< T >;
            n->data = t;
            root = n;

            node->left = n;
            return;
        }
        else if (node->right == 0)
        {
            Node< T >* n = new Node< T >;
            n->data = t;
            root = n;

            node->right = n;
            return;
        }

        unsigned lefth = height(node->left);
        unsigned righth = height(node->right);

        if (lefth <= righth)
        {
            insert(node->left, t);
        }
        else
        {
            insert(node->right, t);
        }       
    }
};

#endif

Main:

#include "binTree.h"

// vectors used in testing
const vector < int > A { 1, -2, 3, -4, 5, -6, 7, -8, 9, -10, 11, -12,
        13, -14, 15 };

// prints out val passed as argument
template < class T > void print ( T& x ) { cout << x << ' '; }

// increments val passed as argument
template < class T > void increment ( T& x ) { x++; }

// decrements val passed as argument
template < class T > void decrement ( T& x ) { x--; }

// prints out attributes, such as size and height of bin tree,
// and prints out data val in each node in inorder, preorder,
// and postorder

template < class T >
void print_attributes ( binTree < T >& tree, const string& name )
{
    cout << name; // print name of tree

    // check if tree is empty
    cout << ": tree is " << ( tree.empty ( ) ? "" : "not " ) << "empty\n";

    // print size and height of tree
    cout << "\tno of nodes    = " << setw ( 2 ) << tree.size ( )
         << "\n\theight of tree = " << setw ( 2 ) << tree.height ( )
         << endl << endl; //*******issue here************

    system("pause");
    return 0;
}
share|improve this question

1 Answer 1

up vote 1 down vote accepted

Firstly, in your class binTree, both the size() and height() methods have the following line:

if (root = 0)

Obviously this should be ==.

The actual stack overflow problem though seems to be caused by your insert function. It takes the first parameter, node by reference. So when you call it with insert(root, t), node ends up as a reference to root. When a new node is allocated in insert, root is set to point to the new node, and this changes the node reference as well.

If you use the debugger to set a breakpoint at the top of your insert function and step through you can watch the values change.

What this means is that root and node are the same thing, so when you set node->left = n or node->right = n the node ends up pointing at itself.

All you should have to do to fix it is change the definition of insert to pass node by value rather than reference:

void insert(Node < T >* node, const T& t) // private version of insert ( )
share|improve this answer
    
Thank you for the reply. I fixed the '= 0' thing and changed the definition of insert, because that does make sense. I've updated the code above to reflect this. However, the same issue still persists unfortunately. The compiler still pointing to the same lines of code and all. –  aredscout Oct 12 '14 at 22:50
    
It fixed the issue for me (in that it no longer went into an infinite loop and crashed). Maybe post a complete compilable example so we can make sure we're starting from exactly the same point. –  Jonathan Potter Oct 12 '14 at 23:11
    
And have you actually tried stepping through in the debugger to see what's going wrong? Just looking at the values of the pointers should be enough to find the error. –  Jonathan Potter Oct 12 '14 at 23:11
    
Well it turns out the issue was just that Visual Studio wasn't actually recompiling my bintree class when I thought it was, and when I fixed that the program worked just fine. –  aredscout Oct 13 '14 at 23:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.