C++ Binary Tree Insertion/Height

Question

I can't seem to figure out where this code is failing. This is for a class assignment, and I must insert into the binary tree in the spot with the lowest height.

I'm getting an apparent segmentation fault in the height function.

class Node {
    public:
        Node();
        Node( int );

    private:
        friend class bT;
        int data;
        Node* left;
        Node* right;
};

class bT {
    public:
        bT();
        virtual void insert( int );
        int height() const;
        unsigned size() const;

    protected:
        Node* root;

    private:
        void insert( Node*&, int );
        int height( Node* ) const;
};

And my main file:

int bT::height() const {
    //Returns -1 when root does not exist
    if ( root == NULL )
        return -1;

    //Calls private recursive method. Uses taller height
    int lheight = height( root->left );
    int rheight = height( root->right );

    if ( lheight > rheight )
        return lheight;
    else
        return rheight;
}


void bT::insert( int x ) {
    //Inserts new node at root if root does not exist
    if ( root == NULL ){
        Node node( x );
        root = &node;
    }

    //Calls private recursive method to insert.
    else {
        int lheight = height( root->left );
        int rheight = height( root->right );

        if ( lheight <= rheight )
            insert( root->left, x );
        else
            insert( root->right, x );
    }
}

int bT::height( Node* r ) const {
    //Base Case: Returns 0 when node does not exist
    if ( r == NULL )
        return 0;

    //Calls private recursive method. Uses taller height
    int lheight = height( r->left );
    int rheight = height( r->right );

    if ( lheight > rheight )
        return 1 + lheight;
    else
        return 1 + rheight;
}

void bT::insert(Node*& r, int x){
    //Base Case: Sets r = new node when node does not exist
    if ( r == NULL ) {
        Node node( x );
        r = &node;
    }

    //Recursive Call: Calls insert function for node with lower height
    else {
        int lheight = height( r->left );
        int rheight = height( r->right );

        if ( lheight <= rheight )
            insert( r->left, x );
        else
            insert( r->right, x );
    }
}

your `root` is a [dangling pointer](http://stackoverflow.com/q/17997228/5980430). The code in your insert method is wrong. — apple apple, Mar 20 '17 at 04:50
@appleapple Thank you, but I've read the page and I'm still confused. How could I fix this without altering the class header (it's given to us and explicitly tells us not to change it). — Tommy, Mar 20 '17 at 04:53
@5980430 in my default constructor for Node, I initialize the left and right pointers to NULL, though. — Tommy, Mar 20 '17 at 05:04

apple apple · Accepted Answer · 2017-03-20T05:12:55.853

1

This code in your insert method would cause dangling pointer

if ( root == NULL ){
   Node node( x );
   root = &node;
}
//root point to invalid address now

A simple fix would be change to dynamic allocation.

if ( root == NULL ){
   Node* node = new Node( x );
   root = node;
}

Since you cannot change the class declaration (and there is no destructor in it), I think you have not learn this, but you need to be careful about memory leak.

edited Mar 20 '17 at 05:12

answered Mar 20 '17 at 05:08

apple apple

10,292
2
16
36

@Tommy I have test it and it work [pretty well](http://coliru.stacked-crooked.com/a/5087c804d4fa3f24). Are you sure you initialize the `left` `right` and `root`, and replace `two` of the above code? – apple apple Mar 20 '17 at 05:56
@Tommy I think that's enough. Have you check the code in my previous comment? BTW, you insert to the wrong place if you want a *complete binary tree*. – apple apple Mar 20 '17 at 06:30
Oh? Where am I inserting wrong? Thanks so much for your patience btw lol – Tommy Mar 20 '17 at 06:32
@Tommy Glad to help, but you might want to check after insert 7 node your tree height is 2 or not (or you do not care about this behavior). – apple apple Mar 20 '17 at 06:45

C++ Binary Tree Insertion/Height

1 Answers1