Member Avatar for 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.

  • 3 Contributors
  • 5 Replies
  • 646 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by Unix*
Member Avatar for 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 ;)

Edited by Unix* because: n/a
commented: nice comment +0
Member Avatar for 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();
}
commented: like you said, yo shouldn post the answers +0
Member Avatar for 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?...:(

Member Avatar for 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. ;)

Edited by Tom Gunn because: n/a
Member Avatar for 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? ;)

commented: No need for apologies. I think you were more right than me. :) +3
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.