CODEWITHSUNDEEP
c++treeheight
Manuel Larrosa
Manuel Larrosa

Reputation: 39

General tree - non binary- height

Sorry for my bad english. Is not my original language.

My problem is that I want to know the height of a general tree, I dont know if that is how it call in english.

The struct of the tree is:

struct GTnode{
    int data;
    nodeGT *fc; //first child
    nodeGT *nb; //next brother
}

Every next brother are in the same level as the first child, and every first child have a +1 level.

This is my code but i'm not sure if is right:

int height(GT *root){
    if(root == null){
        return 0;
    }
    else{
        int max=0;
        int h;
        h = height(root->fc);
        if(h > max){
            max = h;
        }
        max = max + 1;
        h = height(root->nb);
        if(h > max){
           max = h;
        }
        return max;
    }
}

Upvotes: 2

Views: 533

Answers (2)

MSalters
MSalters

Reputation: 180295

I see only one problem: you fail to check if there are children or brothers.

Sure, there's a bit of verbosity. I'd write the code as follows:

int GTnode::height()
{
    int hb = fb ? height(fb) : 0;
    int hc = fc ? height(fc) : 0;
    return std::max(hb, hc+1);
}

Upvotes: 0

Anton Savin
Anton Savin

Reputation: 41341

Your code seems to be fine. I would just make it a bit more compact:

#include <algorithm>

int height(GT *root) {
    return root ? std::max(height(root->fc) + 1, height(root->nb)) : 0;
}

Upvotes: 2

Related Questions