Question:

How do you compute the hight of an m-ary tree?

Printable View

- Dec 4th 2007, 03:58 PMoldguyTree Question
Question:

How do you compute the hight of an m-ary tree? - Dec 16th 2007, 02:43 AMDissimul
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. - Apr 12th 2008, 02:17 AMangel.white
I have a question about this.

In my Data Structures and Algorithms book, it says:

Quote:

Given that we need to store N nodes in a binary tree, the maximum height $\displaystyle H_{max}$ is $\displaystyle 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, $\displaystyle H_{min}$, is determined by the following formula:

$\displaystyle 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.

My question is whether most people compute the root at zero or one.