9
$\begingroup$

I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree start from 0?

$\endgroup$

3 Answers 3

8
$\begingroup$

As Yuval says, there's no standard definition. This is not because computer scientists are indecisive but because it's sometimes more convenient to use one definition and sometimes more convenient to use the other. For example, a full, balanced binary tree of height $h$ has $2^h$ leaves if you define height as number of edges and $2^h-1$ vertices in total if you define height as number of vertices. Each of these statements becomes less convenient if you use the other definition and have to keep writing $h-1$ or $h+1$.

The situation is exactly the same as the natural numbers: sometimes, it's more convenient to say that zero is a natural number (for example, the natural numbers are a semiring only if zero is included); other times, it's more convenient to omit zero (for example, if you always want to be able to divide by a natural number). In fact, similar things happen throughout mathematics. Another example is that it's common to insist that graphs have at least one edge (or at least one vertex) to avoid having to start all your theorems "If $G$ is not trivial, then..."

$\endgroup$
5
$\begingroup$

There is no single accepted definition. Some authors define it as the number of edges, some as the number of nodes. Some authors even use both definitions in different papers. Because of this confusing state of matters, each paper ought to state which definition it uses.

$\endgroup$
0
$\begingroup$

Height of a tree simply means the total number of nodes in that tree on the path from the root node to the deepest node in the tree.For instance,if the height of a tree is 'h' then the minimum number of nodes in that tree can b 'h' and maximum number of nodes can be 2^h-1.

$\endgroup$
1
  • 1
    $\begingroup$ No, as stated in the other answers, there are two "competing" but different definitions of the height of a tree. $\endgroup$ Oct 27, 2014 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.