[Solved]: Is the height of the tree the number of edges or number of nodes?

Problem Detail: 

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?

Asked By : John Swoon

Answered By : David Richerby

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..."

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32357