What is the definition for the height of a tree?

Question

I can't seem to find a definitive answer for this, I'm trying to do some elementary proofs on heaps but here's what's throwing me off a little bit:

Is an empty tree valid? If so, what is its height?
I would think this would be 0.

What is the height of a tree with a single node?
I would think this would be 1 but I have seen definitions where it is 0 (and if this is the case then I don't know how to account for an empty tree).

Viridissa

Answer 1

I think you should take a look at the Dictionary of Algorithms and Data Structures at the NIST website. There definition for height says a single node is height 0.

The definition of a valid tree does include an empty structure. The site doesn't mention the height of such a tree, but based on the definition of the height, it should also be 0.

Trig

Thanks, it's nice to have a reliable source to cite for this (don't think a professor or peer review would consider Wikipedia an acceptable source). Their definitions seem to be a bit contradictory though, they define a tree as either "empty (no nodes), or a root and zero or more subtrees". But their definition of height is defined in terms of the root node. – Viridissa

I agree. I think you should definitly email him (so you can get cited on that page for bringing up this distinction). But considering the definition implies the maximum number of edges from the root to a leaf, we have to say that an empty tree has height 0. – Trig

I just checked the new Cormen and he doesn't make the distinction (p. 1177) either. – Trig

I would say that the height of an empty tree is either -1, or -infinity. Definitely not 0. – Kafiristan

I think, lacking an authoritative source to cite, I'm going to say that an empty tree has an undefined height. This way the number of nodes in a complete binary tree of height h is between 2^h and 2^(h+1)-1. And if you flip it around to solve for h based on n you end up taking log2(0)=undefined when the tree is empty. It makes for a tidy definition and pretty proof at least. – Viridissa

The height of an empty tree is not defined. The height of a tree is the height of the root note of that tree (which is one plus the maximum of the heights of its children, or zero if it has no children). An empty tree does not have a root node, and so cannot be said to have a height. – Rolanda

Actually the new definition says that the height of an empty tree is not defined. – Intercrop

FWIW, CLR appears to suffer from "fear of null" here. Knuth suggests (though the reference is in passing) that the empty tree should have a height of zero. The decision on the part of the NIST to follow the lead of CLR is unfortunate; it needlessly complicates code that wants to use the notion of height. – Giddy

Answer 2

Height of a tree is the length of the path from root of that tree to its farthest node (i.e. leaf node farthest from the root).

A tree with only root node has height 0 and a tree with zero nodes would be considered as empty. An empty tree has height of -1. Please check this.

I hope this helps.

Felice

I believe its a matter of convention used in implementation. As all positive height values and the height value zero would get represented when you have one or more nodes in the tree, you ought to have something to represent an empty tree. So the convention has it as -1. You can have it as any other negative value. Its a matter of implementation as the actual abstraction of the data structure - tree would not cover these things. – Felice

The convention of the empty tree having height -1 actually has some practical use in AVL trees in that it simplifies calculating the balance factor and when to rotate children. This implementation shows it in practice: users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/… – Regan

Answer 3

I have seen it used in both ways (counting a single node as 0 or 1), but the majority of sources would define a root-only tree as a tree of height 0, and would not consider a 0-node tree valid.

Proliferation

Answer 4

If your tree is a recursively defined data structure which may be either empty or a node with a left and right subtree (for example search trees, or your heap), then the natural definition is to assign 0 to the empty tree and 1 + the height of the highest subtree to a nonempty tree.

If your tree is a graph then the natural definition is the longest path from the root to a leaf, so a root-only tree has depth 0. You normally wouldn't even consider empty trees in this case.

Deepset

I'd like to point out that (a) you're obviously right, and (b) the NIST and many other people don't see things (y)our way. I believe this unfortunate state of affairs is principally due to CLR, which suffers from "fear of null". – Giddy

Answer 5

The height of a tree is the length of the longest path to a terminal node in either of its children.

Wikipedia says the height of an empty tree is -1. I disagree. An empty tree is literally just a tree containing one terminal node (a null or special value which represents an empty tree). Since the node has no children, the length of its longest path must be the empty sum = 0, not -1.

Likewise, a non-empty tree has two children, so by definition there is at least a path >= 1 to a terminal node.

We might define our tree as follows:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec height = function
    | Node(left, x, right) -> 1 + max (height left) (height right)
    | Nil -> 0

Rift

"An empty tree is literally just a tree containing one terminal node." Nope, even emptier than that... – Kafiristan

Answer 6

According to Wikipedia, the height of a (sub-)tree with one single node is 0. The height of a tree with no nodes would be -1. But I think it's up to you, how you define the height and your proofs should work with either definition.

Frag

Answer 7

The definition of the height of a rooted tree is the length of the longest path from the root to a leaf, expressed in the number of edges. This definition does not cover the case of an empty tree, as there is no path at all.

However, for practical reasons, it is convenient to define the height of an empty tree as −1. Here are some of those reasons:

1. For non-empty trees we have this rule: the height of the tree is equal to the number of levels in that tree, minus 1. If we extrapolate this rule to an empty tree, then we have 0 levels, and thus a height of −1.

2. A tree with height ℎ has at least ℎ+1 nodes. If the tree is binary, then it has at most 2^ℎ+1−1 nodes. If we substitute −1 for ℎ we get 0 for both expressions, and indeed an empty tree has zero nodes.

3. The height of a tree is one more than the maximum among the heights of the root's subtrees. If the root happens to have no children, we could say it only has "empty" subtrees. And if we consider the height of those empty subtrees to be −1, then we come to the (correct) conclusion that this tree's height is 0.

It would be impractical to define the height of an empty tree as 0, as you would need to define exceptions to the points raised above.

Enough

Answer 8

actully a perfect defn for height of tree is d level of leaf of d longest path from root plus 1..accordin 2 this defn f a tree s empty,it wont b havin any level n v cant consider it had zero,coz level of a root s zero ..so empty tree level is -1,than accordin 2 defn its -1+1=0..so ZERO s d height of empty tree...bt n many book they hav given -1 bt no explanation s given

Saltzman