Results 1 to 3 of 3

Math Help - Tree Question

  1. #1
    Junior Member
    Joined
    Nov 2007
    Posts
    29

    Tree Question

    Question:

    How do you compute the hight of an m-ary tree?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2007
    Posts
    3
    NOTE: I wrote the following without noticing that you said m-ary, not binary. Might still be helpful, probably can be adapted.

    ---

    I'm guessing you already know the definition of height (if we take the root to be at level 0, then the height is the highest level of any node on the tree).

    But if you meant how to compute the height of a tree which is being modelled by a root node which only knows what its left and right nodes are, etc., here is a recursive algorithm:

    To find the height of the subtree with root A, do the following:
    BASE CASE: if A doesn't exist, then the height is -1.
    ---
    1. if A does exist, then define B and C to be the left and right children of A.
    2. Find the height of the subtree with root B and call it H(B).
    3. Find the height of the subtree with root C and call it H(C).
    5. Take whichever of H(B) and H(C) is higher, add 1 to it, and you have your answer.

    Plug the root of the entire tree into this algorithm, and it'll give you the height of the entire tree.

    Hopefully that was what you were looking for.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    I have a question about this.

    In my Data Structures and Algorithms book, it says:

    Given that we need to store N nodes in a binary tree, the maximum height H_{max} is H_{max} = N

    Example: Given three nodes to be stored in a binary tree, what is the maximum height? In this example N is 3. Therefore the maximum height is 3.

    ...

    The minimum height of the tree, H_{min}, is determined by the following formula:

    H_{min} = floor( log_2N)+1

    Example: Given three nodes to be stored in a binary tree, what is the minimum height? Again, N is 3. Therefore the minimum height is 2.
    So, with this definition, if we need to store 1 node in a binary tree, the maximum height is 1, and the minimum height is 1. And it should be apparent that this node is the root. So using this definition, height of the root is 1, not 0.

    My question is whether most people compute the root at zero or one.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 08:40 PM
  2. tree related question ...
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 11th 2011, 12:55 AM
  3. question about graphs / undirected tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 13th 2011, 01:58 PM
  4. Another tree diagram question
    Posted in the Statistics Forum
    Replies: 4
    Last Post: May 15th 2009, 06:43 AM
  5. Spanning tree question.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 7th 2007, 07:01 PM

Search Tags


/mathhelpforum @mathhelpforum