CODEWITHSUNDEEP
c++recursionbinary-tree
user9573040
user9573040

Reputation: 25

Height of binary tree recursively

I get the correct height for all cases expect for when it is an empty binary tree. The size should be zero, but I get 1. I try changing the return after the if statement (get rid of the +1) but that just messes up every other case.

int BTree::recursive_height_helper(BSTNode *n) {

    int rHeight = 0;
    int lHeight = 0;

    if(n->right == NULL || n->left == NULL) return rHeight+lHeight+1;
    rHeight += recursive_height_helper(n->right);
    lHeight += recursive_height_helper(n->left);

     return rHeight+lHeight+1;
}

Upvotes: 1

Views: 93

Answers (2)

Suraj Prakash
Suraj Prakash

Reputation: 41

You can do it using a base case for null node and rest would work just fine.

int Solution::maxDepth(BSTNode* A) {
    if(A == NULL)
        return 0;
    return max(maxDepth(A->left) + 1, maxDepth(A->right) + 1);
}

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66371

You're not handling an empty tree at all (unless your tree has a sentinel root node), and the height of a tree is not the sum of the subtrees' heights.

Also, these lines

int rHeight = 0;
int lHeight = 0;
if(n->right == NULL || n->left == NULL) return rHeight+lHeight+1;

are equivalent to

if(n->right == NULL || n->left == NULL) return 1;

which says that the height of a tree with only one subtree is 1, which would be incorrect even if it were supposed to count nodes.

You can do this with a one-liner:

int BTree::height(BSTNode *n) 
{
    return n == nullptr ? 0 : 1 + std::max(height(n->left), height(n->right));
}

Upvotes: 3

Related Questions