CODEWITHSUNDEEP
c++recursiontree
Tommy
Tommy

Reputation: 23

C++ Binary Tree Insertion/Height

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

Upvotes: 1

Views: 1688

Answers (1)

apple apple
apple apple

Reputation: 10591

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.

Upvotes: 1

Related Questions