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.

3
Contributors
5
Replies
6
Views
7 Years
Discussion Span
Last Post by 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,

or

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 by Unix*: n/a

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)
{
}

return 1 + *heights.rbegin();
}``````
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 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? ;)