C++ Binary Tree Stack Overflow

Question

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;
}

Answer 1

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 ( )