Thread: Tree Question

Question:

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

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.

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 is

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, , is determined by the following formula:



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.