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.

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

Edited 7 Years Ago by Unix*: n/a

Comments
nice comment

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();
}
Comments
like you said, yo shouldn post the answers

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?...:(

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

Edited 7 Years Ago by Tom Gunn: n/a

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

Comments
No need for apologies. I think you were more right than me. :)
This article has been dead for over six months. Start a new discussion instead.