Height of a n-ary tree

[nehemiascr]

Can anyone help me with the algorithm for the height of a n-ary tree, I have been looking and could only found for a binary tree, thanks in advance.

[Unix*]

If you try looking harder its very easy to find, I will not post answers as it is against the rules of these forums,

but try these links... they do provide the answer

http://docs.linux.cz/programming/algorithms/Algorithms-Morris/n_ary_trees.html

or

http://books.google.co.uk/books?id=k0vUmjua41wC&pg=RA1-PA466&lpg=RA1-PA466&dq=n-ary+tree+height+algorithm&source=bl&ots=KLjuHJrjEI&sig=Kv6g5U2_qJgA2M4qOblD1Q4Zygw&hl=en&ei=7MDhSvGpA4_54AbGudGRAg&sa=X&oi=book_result&ct=result&resnum=10&ved=0CCMQ6AEwCQ#v=onepage&q=n-ary%20tree%20height%20algorithm&f=false

if you come up with a simple code conclusion/attempt feel free to post it up if you require further help, but you cant ask people to do everything for you ;)

[Tom Gunn]

Can anyone help me with the algorithm for the height of a n-ary tree, I have been looking and could only found for a binary tree

The basic algorithm is the same. The only difference is that instead of just following the left and right links, you follow n links. Here is the algorithm for a binary tree:

int Height(Node* root)
{
    if (!root) return -1;

    int lh = Height(root->left);
    int rh = Height(root->right);

    return 1 + std::max(lh, rh);
}

For an n-ary tree, the only difference is replacing the two heights with n heights:

int Height(Node* root)
{
    if (!root) return -1;

    std::set<int> heights;

    for (int x = 0; x < N; ++x)
    {
        heights.insert(Height(root->link[x]));
    }

    return 1 + *heights.rbegin();
}

[Unix*]

Funny Tom you gave me negative feedback yesterday for helping someone with a SIMPLE piece of code...but its ok for you to do it?...:(

[Tom Gunn]

Funny Tom you gave me negative feedback yesterday for helping someone with a SIMPLE piece of code...but its ok for you to do it?

I think the difference is clear if you read the questions. The OP you answered was asking for someone to do it for him. This one is actually trying and not making the connection that I showed to be important. But I did solve the problem completely in C++. Pseudo code would have been better, so I will accept your down vote in the spirit it was given. Thank you for keeping me honest. :)

p.s. For what it is worth, I did not test the code, so it might not even compile. ;)

[Unix*]

I think the difference is clear if you read the questions. The OP you answered was asking for someone to do it for him. This one is actually trying and not making the connection that I showed to be important. But I did solve the problem completely in C++. Pseudo code would have been better, so I will accept your down vote in the spirit it was given. Thank you for keeping me honest. :)

p.s. For what it is worth, I did not test the code, so it might not even compile. ;)

My apologies then, I am new to this forum but its clear now..no hard feelings? ;)