CODEWITHSUNDEEP
c++algorithmbinary-treebinary-search-tree
Matcha_boy98
Matcha_boy98

Reputation: 33

Calculating height of a BST returning -1 confusion?

Why are we returning -1 whenthere is no node or nullptr? I cant figure out its logic and how will it cancel with the +1 

int height( BinaryNode * node ) const {
    if ( node == nullptr ) 
        return -1;

    else 
        return 1 + std::max( height( node->left ), height( node->right ) );
    }

Upvotes: 1

Views: 154

Answers (1)

Vlad from Moscow
Vlad from Moscow

Reputation: 310930

The function has a logical error.

If the head node is not equal to nullptr but has no childs the function returns 0. However if there are childs then the head node is countered.

    return 1 + std::max( height( node->left ), height( node->right ) );
          ^^^

Just rewrite the function like

int height( BinaryNode * node ) const 
{
    return node == nullptr ? 0 : 1 + std::max( height( node->left ), height( node->right ) );
}

Or

int height( const BinaryNode * node ) const 
{
    return node == nullptr ? 0 : 1 + std::max( height( node->left ), height( node->right ) );
}

because the tree is not changed by this function.

As the height of the tree can not be negative then it is better to make the return type either as unsigned int or size_t. For example

size_t height( const BinaryNode * node ) const 
{
    return node == nullptr ? 0 : 1 + std::max( height( node->left ), height( node->right ) );
}

Upvotes: 2

Related Questions